A Survey on Algorithmic Aspects of Modular Decomposition

Michel Habib 1 Christophe Paul 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The modular decomposition is a technique that applies but is not restricted to graphs. The notion of module naturally appears in the proofs of many graph theoretical theorems. Computing the modular decomposition tree is an important preprocessing step to solve a large number of combinatorial optimization problems. Since the first polynomial time algorithm in the early 70's, the algorithmic of the modular decomposition has known an important development. This paper survey the ideas and techniques that arose from this line of research.
Type de document :
Article dans une revue
Computer Science Review, Elsevier, 2010, 4 (1), pp.41-59. 〈10.1016/j.cosrev.2010.01.001〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00533514
Contributeur : Christophe Paul <>
Soumis le : dimanche 7 novembre 2010 - 07:43:24
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Michel Habib, Christophe Paul. A Survey on Algorithmic Aspects of Modular Decomposition. Computer Science Review, Elsevier, 2010, 4 (1), pp.41-59. 〈10.1016/j.cosrev.2010.01.001〉. 〈lirmm-00533514〉

Partager

Métriques

Consultations de la notice

168