TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1996

COGA 5-Wheel

Page Content

to Navigation

Preprints 1996

A pratical and efficient algorithm for substitution decomposition
Citation key Report-524-1996
Author Dahlhaus, Elias and Gustedt, Jens and McConnell, Ross
Year 1996
Number 524
Note appeared in SODA'97
Institution Technische Universität Berlin, Institut für Mathematik
Abstract We give a simple recursive algorithm for modular decomposition of undirected graphs that runs in $O(n + m \alpha(m,n))$ time. Previous algorithms with this bound are of theoretical use only. By adding some data structure tricks, we get a much simpler proof of an $O(n+m)$ bound than was previously available. A key element of the algorithm is a procedure for finding a depth-first forest on the complement of a directed graph $G$ in time proportional to the size of $G$.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe