二部图最大权匹配的符号ADD算法

利用代数决策图ADD数据结构，在KM算法基础上，提出了一种二部图最大权匹配的符号ADD算法。该算法引入优先函数概念，将传统的匹配选择转化成布尔运算，“并行”地搜索匹配集合。实验结果表明：与传统算法相比，该算法可以改善问题的状态空间复杂度。     

二部图及匹配算法的描述

二部图是数据库等应用系统的重要的数据结构。在对二部图及匹配的概念做了进一步阐述后，使用类C语言描述了如何识别无向图是否二部图及如何在二部图中寻找最大匹配乃至完全匹配的算法。     

雷达战场抢修人员分配的二部图最优匹配模型

利用辅助决策系统快速生成科学合理的战场抢修人员分配方案,可以有效地提高雷达战场抢修效能．根据雷达战场抢修工作的特点,分析了雷达战场抢修力量分配原则,建立了基于二部图最大匹配算法的战场抢修人员分配模型,并通过算例进行了验证．     

网络最大流问题求解的代数决策图（ADD）技术

Hachtel G．D．和Somenzi F．提出的0-1网络最大流问题的符号有序二叉决策图(OBDD)算法在一定程度上缓减了“状态爆炸”问题，但算法仅局限于求解0-1网络的最大流。Bachar R．I．等提出的代数决策图(ADD)数据结构，是描述伪布尔函数和有限域取值函数的一种有效技术。文中利用ADD存储表示网络及描述网络最大流问题，给出一种求解网络最大流问题的符号ADD技术新思路。实验结果说明了应用ADD技术求解一般网络最大流问题的有效性，可处理0-1网络最大流问题的符号OBDD算法无法处理的非0-1网络。     

网络最大流问题求解的代数决策图(ADD)技术

Hachtel G.D.和 Somenzi F.提出的 0 - 1网络最大流问题的符号有序二叉决策图 (OBDD)算法在一定程度上缓减了“状态爆炸”问题 ,但算法仅局限于求解 0 - 1网络的最大流。Bachar R.I.等提出的代数决策图 (ADD)数据结构 ,是描述伪布尔函数和有限域取值函数的一种有效技术。文中利用 ADD存储表示网络及描述网络最大流问题 ,给出一种求解网络最大流问题的符号 ADD技术新思路。实验结果说明了应用 ADD技术求解一般网络最大流问题的有效性 ,可处理 0 - 1网络最大流问题的符号 OBDD算法无法处理的非 0 - 1网络。     

超级λ_3-最优二部图的充分条件

图的k-限制边连通度是图的边连通度概念的推广,用它可以更加精确的度量网络的可靠性。通过讨论λ3-最优但非超级λ3-最优二部图的性质得到了二部图超级λ3-最优的充分条件。     

优美二部图粘接路的优美性

优美图是图论中的一个重要分支,随着计算机的发展,图的标号在网络和通讯等领域中的应用越来越广泛。文章讨论了优美二部图粘接路所得图的优美性以及这类图的一种混合积的优美性。     

Hamiltonian二部竞赛图中的充分条件

证明了对于一个n×n阶二部竞赛图T,如果T(n,n)满足W(n)条件,则T(n,n)中包含长为4,6,2n的圈,除非T同构于一类特殊的图族。     

Euler图和完全二部图的优美性

给出了Ｅｕｌｅｒ图为优美图的必要条件和完全二部图Ｋｎ,ｍ的优美标号。     

求偶图最大匹配的矩阵算法

深入研究了偶图与其简化邻接矩阵之间的关系，提出了(0，1)—矩阵的无关元对角形概念，利用此概念给出了定理“任一(0，1)—矩阵的项秩与线秩相等”的一种直接简单证明，得到了判断(0，1)—矩阵的无关元集为最大无关元集的充要条件。最后给出了寻找偶图最大匹配的算法——矩阵算法，该算法与匈牙利算法比较具有较高的运算效率和易于在计算机上实现等优点。     

基于二分图最大赋权匹配的网络编码中继选择

针对多用户多中继场景,为了进一步提升系统的吞吐量,需要为用户选择合适的中继协助其传输. 考虑到多址网络编码中继的中继选择问题是一个复杂的优化问题,为了降低其求解复杂度,将中继网络建模为带权二分图,中继选择最优解即转化为图论中求二分图最大赋权匹配问题. 分别将Kuhn和Munkres（KM）算法和贪婪算法应用于多址接入中继网络的中继选择,蒙特卡洛仿真结果表明,KM算法求解的遍历容量略高于贪婪算法.     

基于权重的地图匹配算法

综合考虑车辆行驶的位置、方向以及与GPS定位轨迹的相似性,提出了基于权重的地图匹配算法.该算法将GPS定位数据转换成道路网络的弧的权重,然后根据弧的权重大小来确定车辆当前行驶的道路.在算法中利用道路的拓扑结构使算法简单,使定位数据减少,节约计算资源.仿真结果表明,此算法具有很好的实用价值.     

偶图求最小覆盖的一种算法

以Konig定理作为理论基础,分析偶图的任一最大匹配的饱和顶点集与其任一最小覆盖的关系,得出偶图的任一最小覆盖都包含在该偶图的任一最大匹配的饱和顶点集中的结论。并利用此结论寻求到从偶图的非饱和顶点出发,利用偶图最大匹配求出偶图最小覆盖的一种算法。     

二分图约束的顶点覆盖问题的快速算法

对超大规模集成电路芯片(VLSI)的缺陷修复可归结为受二分图约束的顶点覆盖问题，该问题属于NP完全问题。目前仍不能在多项式时间内对该问题求解。本文应用参数计算理论，将问题化简为与输入问题规模无关的问题来求解。并利用二分图的特性，提出了一种简单、高效的算法，大大提高了修复速度。     

图像多阶特征对集的最优匹配模型

针对图像匹配问题, 提出了一种图像多阶特征对集的最优匹配模型.图像的多阶特征主要是指一阶、二阶和三阶特征, 分别由单个特征点、特征点之间的边或者连接特征点的三角形来定义.最优匹配模型是一个以图像多阶特征为顶点集的加权二分图, 其优点是权重参数可以直接计算, 并能采用Kuhn-Munkras算法求解最大权对集.实验结果表明, 该模型具有很好的鲁棒性, 对于视频序列图像和涂鸦图像, 即使在存在较大缩放、旋转和仿射变换的情况下, 也能获得比较精确的匹配结果, 其准确度通常优于OpenCV中著名的Flann和BruteForce匹配算法.     

基于最大权重独立集的行人检测研究

行人检测是一种基于目标几何和统计特征的目标检测技术,通常包括目标区域的分割和检测,目标检测的准确性和实时性是其重要的评价指标。本文采用可变模板技术进行行人检测,并利用最大权重独立集算法处理帧间的行人匹配。测试结果表明,基于最大权重独立集算法的行人检测能够完成实时的行人检测。     

全双工小蜂窝中基于最大流算法的用户匹配策略

在全双工基站使能的新型小蜂窝中,考虑用户间同频干扰对服务质量的影响,提出了一种最大化满意用户对数的上下行用户匹配策略,用于服务质量敏感的各类新型通信业务.首先依据用户的速率需求和其可达的实际传输速率,构造包含所有潜在满意上下行用户对的匹配可行图;再将可行图转化为单位容量网络,并证明单位容量网络的最大流数目即为最大满意用户对数目,最终由最大流路径推导出最优匹配策略.仿真结果表明,所提策略可获得超出最大和速率策略两倍的满意用户对数,且仅具有多项式级的复杂度.