The Symbolic OBDD Algorithm for Finding Optimal Semi-matching in Bipartite Graphs

Tianlong  Gu; Liang  Chang; Zhoubo  Xu

doi:10.4236/cn.2011.32009

Tianlong Gu, Liang Chang, Zhoubo Xu

Abstract: 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.

Keywords: Bipartite Graphs, Semi-Matching, Load Balancing, Ordered Binary Decision Diagram

Cite this paper: nullT. Gu, L. Chang and Z. Xu, "The Symbolic OBDD Algorithm for Finding Optimal Semi-matching in Bipartite Graphs," Communications and Network, Vol. 3 No. 2, 2011, pp. 65-72. doi: 10.4236/cn.2011.32009.

References

[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, “Network Flows: Theory, Algorithms, and Applications,” Pearson Education Inc., Prentice Hall, Upper Saddle River, 1993.

[2] Z. Galil, “Efficient Algorithm for Finding Maximum Matching in Graphs,” ACM Computing Surveys, Vol. 18, No. 1, 1986, pp. 23-37. doi:10.1145/6462.6502

[3] N. Harvey, R. Ladner, L. Lovasz and T. Tamir, “Semi-matchings for Bipartite Graphs and Load Balancing,” Journal of Algorithms, Vol. 59, No.1, 2006, pp. 53-78. doi:10.1145/6462.6502

[4] E. Lawler, “Combinatorial Optimization: Networks and Matroids,” Dover Publications Inc., New York, 2001.

[5] R. E. Bryant, “Graph-Based Algorithms for Boolean Function Manipulation,” IEEE Transaction on Computer, Vol. 35, No. 8, 1986, pp.677-691. doi:10.1109/TC.1986.1676819

[6] R. E. Bryant, “Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams,” ACM Computing Surveys, Vol. 24, No. 3, 1992, pp. 293-318. doi:10.1145/136035.136043

[7] S. B. Akers, “Binary Decision Diagrams,” IEEE Transaction on Computer, Vol. 27, No. 6, 1978, pp. 509-516. doi:10.1109/TC.1978.1675141

[8] D. Sieling and R. Drechsler, “Reduction of OBDDs in Linear Time,” Information Processing Letters, Vol. 48, No. 3, 1993, pp. 139-144. doi:10.1016/0020-0190(93)90256-9

[9] D. Sieling and I. Wegener, “Graph Driven BDDs—A New Data Structure for Boolean Functions,” Theoretical Computer Science, Vol. 141, No. 1-2, 1995, pp. 283-310. doi:10.1016/0304-3975(94)00078-W

[10] G. D. Hachtel and F. Somenzi, “A Symbolic Algorithm for Maximum Flow in 0-1 Networks,” Formal Methods in System Design, Vol. 10, No. 2-3, 1997, pp. 207-219. doi:10.1023/A:1008651924240

[11] T. L. Gu and Z. B. Xu, “The Symbolic Algorithms for Maximum Flow in Networks,” Computers & Operations Research, Vol. 34, No. 2, 2007, pp. 799-816. doi:10.1016/j.cor.2005.05.009

[12] F. Somenzi, “CUDD: CU Decision Diagram Package Release 2.3.1,” 2001. http://vlsi.Colorado.edu/