Inhalt des Dokuments
Preprint 524-1996
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- A pratical and efficient algorithm for substitution decomposition
- Authors
- Elias Dahlhaus, Jens Gustedt, and Ross McConnell
- Publication
- appeared in SODA'97
- Classification
-
not available
- Keywords
-
not available
- Abstract
-
We give a simple recursive algorithm for modular decomposition of undirected graphs that runs in O(n + m α(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.
- Source
- Download as [ps.gz]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe