Graph decompositions and factorizing permutations
Authors:
- M. HabibMHM. Habib
- 22 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 132-143
Abstract
A factorizing permutation of a given undirected graph is simply a permutation of the vertices in which all decomposition sets appear to be factors. Such a concept seems to play a central role in recent papers dealing with graph decomposition. We apply it to modular decomposition and we propose a linear algorithm that computes the whole decomposition tree when a factorizing permutation is provided. This algorithm can be seen as a common generalization of (Ma and Hsu, 1991) for modular decomposition of chordal graphs and (Habib et al., 1995) for inheritance graph decomposition. It also suggests many new decomposition algorithms for various notions of graph decompositions.Keywords
This publication has 4 references indexed in Scilit:
- Efficient and Practical Algorithms for Sequential Modular DecompositionJournal of Algorithms, 2001
- A linear algorithm to decompose inheritance graphs into modulesAlgorithmica, 1995
- Substitution decomposition on chordal graphs and applications1991
- A Combinatorial Decomposition TheoryCanadian Journal of Mathematics, 1980