期刊文献+
共找到2篇文章
< 1 >
每页显示 20 50 100
The Symbolic OBDD Algorithm for Finding Optimal Semi-matching in Bipartite Graphs
1
作者 Tianlong Gu Liang Chang Zhoubo Xu 《Communications and Network》 2011年第2期65-72,共8页
The optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canoni... The optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic OBDD formulation and algorithm for the optimal semi-matching problem in bipartite graphs. The symbolic algorithm is initialized by heuristic searching initial matching and then iterates through generating residual network, building layered network, backward traversing node-disjoint augmenting paths, and updating semi-matching. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Our simulations show that symbolic algorithm has better performance, especially on dense and large graphs. 展开更多
关键词 BIPARTITE Graphs semi-matching Load Balancing ORDERED Binary Decision DIAGRAM
下载PDF
Perfect 1-k Matchings of Bipartite Graphs
2
作者 Wenduan Dai Yan Liu Yanfang Wu 《Open Journal of Discrete Mathematics》 2024年第4期43-53,共11页
Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is inc... Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching. 展开更多
关键词 Bipartite Graph semi-matching Perfect 1-k Matching k-Elementary Graph
下载PDF
上一页 1 下一页 到第
使用帮助 返回顶部