Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00072825
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 11:03:02 AM
Last modification on : Friday, February 26, 2021 - 3:28:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:23:52 PM

Identifiers

  • HAL Id : inria-00072825, version 1

Collections

Citation

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

Share

Metrics

Record views

208

Files downloads

235