Simple, Linear-Time Modular Decomposition

Abstract : Modular decomposition is fundamental for many important problems in algorithmic graph-theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been a drive towards a practical, linear-time algorithm for the problem. Despite considerable effort, such an algorithm has remained elusive. The linear-time algorithms to date are impractical and of mainly theoretical interest. In this paper we present the first simple, linear-time algorithm to compute the modular decomposition tree of an undirected graph.
Type de document :
Communication dans un congrès
ICALP: International Colloquium on Automata, Languages and Programming, Jul 2008, Reykjavik, Iceland. pp.634-645, 2008, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324557
Contributeur : Christophe Paul <>
Soumis le : jeudi 25 septembre 2008 - 14:09:22
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00324557, version 1

Collections

Citation

Marc Tedder, Derek Corneil, Michel Habib, Christophe Paul. Simple, Linear-Time Modular Decomposition. ICALP: International Colloquium on Automata, Languages and Programming, Jul 2008, Reykjavik, Iceland. pp.634-645, 2008, Lecture Notes in Computer Science. 〈lirmm-00324557〉

Partager

Métriques

Consultations de la notice

90