A Novel Symbolic Algorithm for Maximum Weighted Matching in Bipartite Graphs
Abstract: The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.
Cite this paper: nullT. Gu, L. Chang and Z. Xu, "A Novel Symbolic Algorithm for Maximum Weighted Matching in Bipartite Graphs," International Journal of Communications, Network and System Sciences, Vol. 4 No. 2, 2011, pp. 111-121. doi: 10.4236/ijcns.2011.42014.
References

[1]   R. K. Ahuja, T. L. Magnanti and J. B. Orlin, “Network Flows: Theory, Algorithms, and Applications,” Pearson Education Inc., Prentice Hall, Englewood Cliffs, 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]   H. W. Kuhn, “The Hungarian Method for Assignment Problem,” Naval Research Logistics Quarterly, Vol. 2, No. 1-2, 1955, pp. 83-97. doi:10.1002/nav.3800020109

[4]   J. Munkres, “Algorithms for Assignment and Transportation Problems,” Journal of SIAM, Vol. 5, No. 1, 1957, pp. 32-38.

[5]   H. N. Gabow and R. E. Tarjan, “Faster Scaling Algorithms for Network Problems,” SIAM Journal on Computing, Vol. 18, No. 5, 1989, pp. 1013-1036. doi:10.1137/0218069

[6]   A. V. Goldberg, S. A. Plotkin and P. M. Vaidya, “Sublinear Time Parallel Algorithms for Matching and Related Problems,” Journal of Algorithms, Vol. 14, No. 2, 1993, pp. 180-213. doi:10.1006/jagm.1993.1009

[7]   J. B. Orlin and R. K. Ahuja, “New Scaling Algorithms for the Assignment and Minimum Cycle Mean Problems,” Sloan Working Paper 2019-88, Solan School of Management, Massachusetts Institute of Technology, Cambridge, 1988.

[8]   A. V. Goldberg and R. Kennedy, “An Efficient Cost Scaling Algorithm for the Assignment Problem,” Mathematical Programming, Vol. 71, No. 2, 1995, pp. 153-178. doi:10.1007/BF01585996

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

[10]   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

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

[12]   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

[13]   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

[14]   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

[15]   R. I. Bahar, E. A. Frohm, C. M. Gaona, et al. “Algebraic Decision Diagrams and Their Applications,” Formal Methods in Systems Design, Vol. 10, No. 2-3, 1997, pp. 171-206. doi:10.1023/A:1008699807402

[16]   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

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

[18]   The LEDA User Manual, 2010. http://www.algorithmic-solutions.com

Top