Unifying Two Graph Decompositions with 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 : 2007

Unifying Two Graph Decompositions with Modular Decomposition

Résumé

We introduces the umodules, a generalisation of the notion of graph module. The theory we develop captures among others undirected graphs, tournaments, digraphs, and $2-$structures. We show that, under some axioms, a unique decomposition tree exists for umodules. Polynomial-time algorithms are provided for: non-trivial umodule test, maximal umodule computation, and decomposition tree computation when the tree exists. Our results unify many known decomposition like modular and bi-join decomposition of graphs, and a new decomposition of tournaments.

Dates et versions

lirmm-00325376 , version 1 (29-09-2008)

Identifiants

Citer

Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy, Fabien de Montgolfier. Unifying Two Graph Decompositions with Modular Decomposition. ISAAC'07: 18th International Symposium on Algorithms and Computation, Dec 2007, Sendai, Japan. pp.52-64, ⟨10.1007/978-3-540-77120-3_7⟩. ⟨lirmm-00325376⟩
112 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More