Discrete Mathematics & Theoretical Computer Science
| author: | Christian Capelle and Michel Habib and Fabien de Montgolfier |
|---|---|
| title: | Graph Decompositions and Factorizing Permutations |
| keywords: | Graph algorithms, graph decompositions, modular decomposition |
| abstract: | A factorizing permutation of a given graph is simply a
permutation of its vertices of which all decomposition sets are
factors. Such a concept appears to play a central role in
recent papers dealing with graph decomposition. It is applied here
for modular decomposition of directed graphs, and we
propose a simple linear algorithm that computes the whole decomposition tree
when a factorizing permutation is provided.
The approach of using
parenthesized factors of a list was first used by Hopcroft and Tarjan
for triconnected components search .
Our algorithm can be seen as a common generalization of Hsu and Ma
for modular decomposition of chordal graphs and
Habib, Huchard and Spinrad for inheritance graphs
decomposition. It
also
suggests many new decomposition algorithms for various notions of
graph decompositions.
If your browser does not display the abstract correctly (because of the different mathematical symbols) you can look it up in the PostScript or PDF files. |
| reference: | Christian Capelle and Michel Habib and Fabien de Montgolfier (2002), Graph Decompositions andFactorizing Permutations, Discrete Mathematics and Theoretical Computer Science 5, pp. 55-70 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dm050104.ps.gz (57 K) |
| ps-source: | dm050104.ps (216 K) |
| pdf-source: | dm050104.pdf (144 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.