A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2004

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

Résumé

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.
Fichier principal
Vignette du fichier
swat04.pdf (169.14 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00159601 , version 1 (04-07-2007)

Identifiants

Citer

Michel Habib, Fabien de Montgolfier, Christophe Paul. A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension. SWAT 2004 - 9th Scandinavian Workshop on Algorithm Theory, Jul 2004, Humlebaek, Denmark. pp.187-198, ⟨10.1007/978-3-540-27810-8_17⟩. ⟨hal-00159601⟩
149 Consultations
808 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More