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.

Biconnectivity on Symbolically Represented Graphs: A Linear Solution.

GENTILINI, Raffaella;
2003

Abstract

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.
9783540206958
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11391/43339
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
social impact