We present an algorithm that computes in a linear number of symbolic steps (O(|V|)) the strongly connected components (sccs) of a graph G = <V,E> represented by an Ordered Binary Decision Diagram (OBDD). This result matches the complexity of the (celebrated) Tarjan's algorithm operating on explicit data structures. To date, the best algorithm for the above problem works in Θ(|V|log|V|) symbolic steps ([BGS00]).
Computing strongly connected components in a linear number of symbolic steps
PIAZZA, Carla;POLICRITI, Alberto
2003-01-01
Abstract
We present an algorithm that computes in a linear number of symbolic steps (O(|V|)) the strongly connected components (sccs) of a graph G =File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
p573-gentilini.pdf
non disponibili
Tipologia:
Altro materiale allegato
Licenza:
Non pubblico
Dimensione
838.06 kB
Formato
Adobe PDF
|
838.06 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
