A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension

Abstract : The first polynomial time algorithm (O(n^4)) for modular decomposition appeared in 1972 and since then there have been incremental improvements, eventually resulting in linear-time algorithms. Although having optimal time complexity these algorithms are quite complicated and difficult to implement. In this paper we present an easily implementable linear-time algorithm for modular decomposition. This algorithm uses the notion of factorizing permutation and a new data-structure, the Ordered Chain Partitions.
Type de document :
Communication dans un congrès
Torben Hagerup, Jyrki Katajainen. 9th Scandinavian Workshop on Algorithm Theory, 2004, Humlebaek, Denmark. springer, pp.187-198, 2004, LNCS vol. 3111
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-00159601
Contributeur : Fabien De Montgolfier <>
Soumis le : mercredi 4 juillet 2007 - 11:43:07
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : jeudi 8 avril 2010 - 22:27:49

Fichier

swat04.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00159601, version 1

Collections

Citation

Michel Habib, Fabien De Montgolfier, Christophe Paul. A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension. Torben Hagerup, Jyrki Katajainen. 9th Scandinavian Workshop on Algorithm Theory, 2004, Humlebaek, Denmark. springer, pp.187-198, 2004, LNCS vol. 3111. 〈hal-00159601〉

Partager

Métriques

Consultations de la notice

141

Téléchargements de fichiers

234