An ADD-based Algorithm for Maximum Weight Matching in Bipartite Graphs
Zhoubo Xu · Journal of Guilin University of Electronic Technology · 2005
Abstrcat Algebraic Decision Diagram is a new efficient approach to solve combinatorial optimization problems. In this paper, according to Kuhn-Munkres algorithm, the authors propose a symbolic algorithm based on ADD data structure for the maximum weight matching in bipartite graphs. By using symbolic manipulations, this algorithm introduces the priority function applied to a parallel search for the set of matching. Compared with the traditional algorithms, the experimental results demonstrate that the algorithm can improve state space complexity of the problem.