Unifying Two Graph Decompositions with Modular Decomposition

Abstract : 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.
Type de document :
Communication dans un congrès
Takeshi Tokuyama. ISAAC'07: 18th International Symposium on Algorithms and Computation, Dec 2007, Sendai, Japan. Springer Berlin / Heidelberg, LNCS (4835), pp.52-64, 2007, Algorithms and Computation. 〈http://www.nishizeki.ecei.tohoku.ac.jp/isaac07/〉. 〈10.1007/978-3-540-77120-3_7〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00325376
Contributeur : Binh-Minh Bui-Xuan <>
Soumis le : lundi 29 septembre 2008 - 10:15:00
Dernière modification le : jeudi 24 mai 2018 - 15:59:20

Identifiants

Collections

Citation

Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy, Fabien De Montgolfier. Unifying Two Graph Decompositions with Modular Decomposition. Takeshi Tokuyama. ISAAC'07: 18th International Symposium on Algorithms and Computation, Dec 2007, Sendai, Japan. Springer Berlin / Heidelberg, LNCS (4835), pp.52-64, 2007, Algorithms and Computation. 〈http://www.nishizeki.ecei.tohoku.ac.jp/isaac07/〉. 〈10.1007/978-3-540-77120-3_7〉. 〈lirmm-00325376〉

Partager

Métriques

Consultations de la notice

167