Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download
Contributor : Vincent Limouzy <>
Submitted on : Monday, March 13, 2006 - 10:43:55 AM
Last modification on : Friday, May 1, 2020 - 1:08:54 AM
Document(s) archivé(s) le : Saturday, April 3, 2010 - 8:18:57 PM




Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy, Fabien de Montgolfier. Homogeneity vs. Adjacency: generalising some graph decomposition algorithms. WG: Graph-Theoretic Concepts in Computer Science, Jun 2006, Bergen, Norway. pp.278-288, ⟨10.1007/11917496_25⟩. ⟨hal-00020188⟩



Record views


Files downloads