Biconnectivity on Symbolically Represented Graphs: A Linear Solution

摘要

We define an algorithm for determining, in a linear number of symbolic steps, the biconnected components of a graph implicitly represented with Ordered Binary Decision Diagrams (OBDDs). Working on symbolically represented data has potential: the standards achieved in graph sizes (playing a crucial role, for example, in verification, VLSI design, and CAD) are definitely higher. On the other hand, symbolic algorithm's design generates constraints as well. For example, Depth First Search is not feasible in the symbolic setting, and our algorithm relies on the use of spine-sets, introduced in [8] for strongly connected components, as its substitute. Our approach suggests a symbolic framework to tackle those problems which are naturally solved by a DFS-based algorithm in the standard case.