Simple, Linear-Time Modular Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Simple, Linear-Time Modular Decomposition

Résumé

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.
Fichier non déposé

Dates et versions

lirmm-00324557 , version 1 (25-09-2008)

Identifiants

  • HAL Id : lirmm-00324557 , version 1

Citer

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. ⟨lirmm-00324557⟩
296 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More