Partially complemented representations of digraphs

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 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, 5, pp.147-168. 〈http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/172〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00100846
Contributeur : Jens Gustedt <>
Soumis le : jeudi 26 novembre 2009 - 10:59:32
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:53:52

Fichier

514.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00100846, version 1

Collections

Citation

Elias Dahlhaus, Jens Gustedt, Ross M. Mcconnell. Partially complemented representations of digraphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, 5, pp.147-168. 〈http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/172〉. 〈inria-00100846〉

Partager

Métriques

Consultations de la notice

249

Téléchargements de fichiers

148