Simple, Linear-Time Modular Decomposition
International audience 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...
Main Authors: | , , , |
---|---|
Other Authors: | , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2008
|
Subjects: | |
Online Access: | https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324557 |
id |
ftunimontpellier:oai:HAL:lirmm-00324557v1 |
---|---|
record_format |
openpolar |
spelling |
ftunimontpellier:oai:HAL:lirmm-00324557v1 2023-05-15T16:48:07+02:00 Simple, Linear-Time Modular Decomposition Tedder, Marc Corneil, Derek Habib, Michel Paul, Christophe Department of Computer Science University of Toronto (DCS) University of Toronto Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Algorithmes, Graphes et Combinatoire (ALGCO) Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS) Reykjavik, Iceland 2008-07-06 https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324557 en eng HAL CCSD lirmm-00324557 https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324557 ICALP: International Colloquium on Automata, Languages and Programming https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324557 ICALP: International Colloquium on Automata, Languages and Programming, Jul 2008, Reykjavik, Iceland. pp.634-645 [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] info:eu-repo/semantics/conferenceObject Conference papers 2008 ftunimontpellier 2023-02-07T23:40:38Z International audience 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. Conference Object Iceland Université de Montpellier: HAL |
institution |
Open Polar |
collection |
Université de Montpellier: HAL |
op_collection_id |
ftunimontpellier |
language |
English |
topic |
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
spellingShingle |
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Tedder, Marc Corneil, Derek Habib, Michel Paul, Christophe Simple, Linear-Time Modular Decomposition |
topic_facet |
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
description |
International audience 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. |
author2 |
Department of Computer Science University of Toronto (DCS) University of Toronto Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Algorithmes, Graphes et Combinatoire (ALGCO) Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS) |
format |
Conference Object |
author |
Tedder, Marc Corneil, Derek Habib, Michel Paul, Christophe |
author_facet |
Tedder, Marc Corneil, Derek Habib, Michel Paul, Christophe |
author_sort |
Tedder, Marc |
title |
Simple, Linear-Time Modular Decomposition |
title_short |
Simple, Linear-Time Modular Decomposition |
title_full |
Simple, Linear-Time Modular Decomposition |
title_fullStr |
Simple, Linear-Time Modular Decomposition |
title_full_unstemmed |
Simple, Linear-Time Modular Decomposition |
title_sort |
simple, linear-time modular decomposition |
publisher |
HAL CCSD |
publishDate |
2008 |
url |
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324557 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ICALP: International Colloquium on Automata, Languages and Programming https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324557 ICALP: International Colloquium on Automata, Languages and Programming, Jul 2008, Reykjavik, Iceland. pp.634-645 |
op_relation |
lirmm-00324557 https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324557 |
_version_ |
1766038239039193088 |