Unifying Two Graph Decompositions with Modular Decomposition

DOI10.1007/978-3-540-77120-3_7MaRDI QIDQ5387745zbMATH OpenOpenAlexFDO

Authors Binh-Minh Bui-Xuan, Vincent Limouzy, Fabien De Montgolfier, M. A. Habib

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0604065

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• Algorithmic aspects of a general modular decomposition theory
• Graph-Theoretic Concepts in Computer Science
• Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms
• Incremental modular decomposition
• A survey of the algorithmic aspects of modular decomposition

Cited in

(8)

• Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms
• The orientation of modules based on graph decomposition
• A Representation Theorem for Union-Difference Families and Application
• Decompositions and forcing relations in graphs and other combinatorial structures
• On unimodular tournaments
• Matricial characterization of tournaments with maximum number of diamonds
• From modular decomposition trees to rooted median graphs
• The rank-width of edge-coloured graphs

This page was built for publication: Unifying Two Graph Decompositions with Modular Decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387745)