Unifying Two Graph Decompositions with Modular Decomposition
Unifying Two Graph Decompositions with Modular Decomposition
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.
Soumis \`a ISAAC 2007
- University of Paris France
- French National Centre for Scientific Research France
- UNIVERSITE PARIS DESCARTES France
- University of Montpellier France
- LIAFA France
FOS: Computer and information sciences, Tournaments decomposition, Modular Decomposition, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Discrete Structures, Computer Science - Data Structures and Algorithms, Umodule, Data Structures and Algorithms (cs.DS), Algorithms
FOS: Computer and information sciences, Tournaments decomposition, Modular Decomposition, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Discrete Structures, Computer Science - Data Structures and Algorithms, Umodule, Data Structures and Algorithms (cs.DS), Algorithms
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!