A Pratical and Efficient Algorithm for Substitution Decomposition

Elias Dahlhaus Jens Gustedt 1 Ross M. Mcconnell
1 TUB - Technische Universität Berlin
Abstract : We give a simple recursive algorithm for modular decomposition of undirected graphs that runs in O(n + m alpha(m,n)) time. Previous algorithms with this bound are of theoretical use only. By adding some data structure tricks, we get a much simpler proof of an O(n+m) bound than was previously available. A key element of the algorithm is a procedure for finding a depth-first forest on the complement of a directed graph G in time proportional to the size of G.
Type de document :
Communication dans un congrès
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97), 1997, New Orleans, United States. SIAM, pp.26-35, 1997
Liste complète des métadonnées
https://hal.inria.fr/inria-00549669
Contributeur : Jens Gustedt <>
Soumis le : mercredi 22 décembre 2010 - 12:04:46
Dernière modification le : dimanche 20 mai 2018 - 20:20:10

Identifiants

  • HAL Id : inria-00549669, version 1

Citation

Elias Dahlhaus, Jens Gustedt, Ross M. Mcconnell. A Pratical and Efficient Algorithm for Substitution Decomposition. Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97), 1997, New Orleans, United States. SIAM, pp.26-35, 1997. 〈inria-00549669〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

22

Contact


archive-ouverte@inria.fr