Advances and Applications in Discrete Mathematics
Volume 6, Issue 2, Pages 125 - 138
(October 2010)
|
|
THE SYMBOLIC OBDD ALGORITHM FOR MAXIMUM CARDINALITY MATCHING IN BIPARTITE GRAPHS
Tianlong Gu, Liang Chang and Zhoubo Xu
|
Abstract: The maximum cardinality matching problem in bipartite graphs is one of classic combinatorial optimization problems, and arises in many different application settings where we often wish to find the proper way to pair objects or people together to achieve some desired goal. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate the Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching the nodes and edges implicitly. We present novel symbolic OBDD formulation and algorithm for maximum cardinality matching in bipartite graphs. The symbolic algorithm is initialized by heuristic search matching and then iterates through building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments give the fact that symbolic algorithm is competitive with traditional algorithms, especially on dense and large graphs. |
Keywords and phrases: symbolic algorithms, maximum cardinality matching, ordered binary decision diagram, bipartite graphs. |
|
Number of Downloads: 219 | Number of Views: 701 |
|