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