Discrete Mathematics & Theoretical Computer Science

DMTCS

Volume 5 n° 1 (2002), pp. 55-70


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.


Automatically produced on Wed Apr 24 22:46:01 CEST 2002 by ifalk