IRIS - Res&Arch Institutional Research Information System - Research & Archive
Anagrafe della Ricerca dell'Università degli Studi di Perugia.
EnglishWe 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.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | Biconnectivity on Symbolically Represented Graphs: A Linear Solution. |
| Autori: | |
| Data di pubblicazione: | 2003 |
| Rivista: | |
| 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. |
| Handle: | http://hdl.handle.net/11391/43339 |
| ISBN: | 9783540206958 |
| Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
Copyright © 2020