Discrete Mathematics & Theoretical Computer Science, Vol 5 (2002)

Font Size:  Small  Medium  Large
DMTCS vol 5 no 1 (2002), pp. 147-168

Discrete Mathematics & Theoretical Computer Science


Volume 5 n° 1 (2002), pp. 147-168

author:Elias Dahlhaus and Jens Gustedt and Ross M. McConnell
title:Partially Complemented Representations of Digraphs
keywords:efficient graph algorithms, data structures, search strategies, modular decomposition
abstract:A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalence relation where two digraphs are equivalent if one can be obtained from the other by a sequence of such operations. We show that given an adjacency-list representation of a digraph G, many fundamental graph algorithms can be carried out on any member G' of G's equivalence class in O(n+m) time, where m is the number of arcs in G, not the number of arcs in G' . This may have advantages when G' is much larger than G. We use this to generalize to digraphs a simple O(n + m log n) algorithm of McConnell and Spinrad for finding the modular decomposition of undirected graphs. A key step is finding the strongly-connected components of a digraph F in G's equivalence class, where F may have ~(m log n) arcs.

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: Elias Dahlhaus and Jens Gustedt and Ross M. McConnell (2002), Partially Complemented Representations of Digraphs, Discrete Mathematics and Theoretical Computer Science 5, pp. 147-168
bibtex:For a corresponding BibTeX entry, please consider our BibTeX-file.
ps.gz-source:dm050110.ps.gz (66 K)
ps-source:dm050110.ps (271 K)
pdf-source:dm050110.pdf (184 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 Fri Jun 7 18:19:20 CEST 2002 by gustedt