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

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/