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

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 = 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]).
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/745858
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 70
  • ???jsp.display-item.citation.isi??? 53
social impact