Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms

Abstract : In this paper, a new general decomposition theory inspired from modular graph decomposition is presented. Our main result shows that, within this general theory, most of the nice algorithmic tools developed for modular decomposition are still efficient. This theory not only unifies the usual modular decomposition generalisations such as modular decomposition of directed graphs or decomposition of 2-structures, but also star cutsets and bimodular decomposition. Our general framework provides a decomposition algorithm which improves the best known algorithms for bimodular decomposition.
Type de document :
Communication dans un congrès
Fedor V. Fomin. WG'06: 32th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2006, Bergen, Norway, Springer Berlin / Heidelberg, 4271, pp.278-288, 2006, Lecture Notes in Computer Science. 〈http://www.ii.uib.no/wg06/〉. 〈10.1007/11917496_25〉
Liste complète des métadonnées

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

Lien texte intégral

Identifiants

Collections

Citation

Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy, Fabien De Montgolfier. Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms. Fedor V. Fomin. WG'06: 32th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2006, Bergen, Norway, Springer Berlin / Heidelberg, 4271, pp.278-288, 2006, Lecture Notes in Computer Science. 〈http://www.ii.uib.no/wg06/〉. 〈10.1007/11917496_25〉. 〈lirmm-00325379〉

Partager

Métriques

Consultations de la notice

107