zbMATH — the first resource for mathematics

The symbolic OBDD algorithm for maximum cardinality matching in bipartite graphs. (English) Zbl 1219.68122
Summary: The maximum cardinality matching problem in bipartite graphs is a classic combinatorial optimization problems and arises in many different application settings where we often wish to find the proper way to pair objects or people together to achieve some desired goal. 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 the nodes and edges implicitly. We present a novel symbolic OBDD formulation and algorithm for maximum cardinality matching in bipartite graphs. The symbolic algorithm is initialized by heuristic search matching and then iterates through building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments give the fact that the symbolic algorithm is competitive with traditional algorithms, especially on dense and large graphs.
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C59 Approximation methods and heuristics in mathematical programming
Full Text: Link