Partially Complemented Representations of Digraphs

Elias Dahlhaus Jens Gustedt 1 Ross M. Mcconnell
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalen- ce relation where two digraphs are equivalent if one can be obtained from the other by a sequence of such operations. We show that given an adjacency-li- st representation of a digraph G, many fundamental graph algorithms can be carried out on any member G' of G's equivalence class in O(n+m) time, where m is the number of arcs in G, not the number of arcs in G' . This may have advantages when G' is much larger than G. We use this to generalize to digraphs a simple O(n + m \log n) algorithm of McConnell and Spinrad for finding the modular decomposition of undirected graphs. A key step is finding the strongly-connected components of a digraph F in G's equivalence class, where F may have \omega(m \log n) arcs.
Type de document :
[Research Report] RR-3832, INRIA. 1999, pp.24
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:03:02
Dernière modification le : dimanche 20 mai 2018 - 20:20:10
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:23:52



  • HAL Id : inria-00072825, version 1



Elias Dahlhaus, Jens Gustedt, Ross M. Mcconnell. Partially Complemented Representations of Digraphs. [Research Report] RR-3832, INRIA. 1999, pp.24. 〈inria-00072825〉



Consultations de la notice


Téléchargements de fichiers