TITLE:
A Novel Symbolic Algorithm for Maximum Weighted Matching in Bipartite Graphs
AUTHORS:
Tianlong Gu, Liang Chang, Zhoubo Xu
KEYWORDS:
Bipartite Graphs, Weighted Matching, Symbolic Algorithm, Algebraic Decision Diagram (ADD), Ordered Binary Decision Diagram (OBDD)
JOURNAL NAME:
International Journal of Communications, Network and System Sciences,
Vol.4 No.2,
February
26,
2011
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.