Elias Dahlhaus ; Jens Gustedt ; Ross M. Mcconnell - Partially complemented representations of digraphs

dmtcs:303 - Discrete Mathematics & Theoretical Computer Science, January 1, 2002, Vol. 5 - https://doi.org/10.46298/dmtcs.303
Partially complemented representations of digraphsArticle

Authors: Elias Dahlhaus 1; Jens Gustedt ORCID2; Ross M. Mcconnell 3

  • 1 Department. of Computer Science [Cologne]
  • 2 Software Tools for Telecommunications and Distributed Systems
  • 3 Computer Science Department, Colorado State University

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 equivalence 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-list 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 ~(m log n) arcs.


Volume: Vol. 5
Published on: January 1, 2002
Imported on: March 26, 2015
Keywords: algorithmes de graphes,modular decomposition,data structures,search strategies,structures de données,stratégies de recherche,décomposition modulaire,efficient graph algorithms,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]

5 Documents citing this article

Consultation statistics

This page has been seen 327 times.
This article's PDF has been downloaded 466 times.