On efficient implicit OBDD-based algorithms for maximal matchings

摘要

The maximal matching problem, i.e., the computation of a matching that is not a proper subset of another matching, is a fundamental optimization problem, and maximal matching algorithms have been used as submodules for problems like maximal node-disjoint paths or maximum flow. Since in some applications very large graphs have to be processed, a research branch has emerged which is concerned with the design and analysis of implicit algorithms for classical graph problems. Input graphs are given as characteristic Boolean functions of their edge sets, and problems have to be solved by functional operations. As OBDDs. Which are closely related to deterministic finite automata, are a well-known data structure for Boolean functions, OBDD-based algorithms are used as a heuristic approach to handle very large graphs. Here, an implicit OBDD-based maximal matching algorithm is presented that uses only a polylogarithmic number of functional operations with respect to the number of vertices of the input graph. In order to investigate the algorithm's behavior on large and structured networks, it is analyzed on grid graphs. It is shown that the overall running time and the space requirement is also polylogarithmic. Furthermore, we present another algorithm similar to the well-known Karp-Sipser approach and we investigate the representation size of maximal matchings.