Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient and Practical Modular Decomposition (1997)
| Content Provider | CiteSeerX |
|---|---|
| Author | Dahlhaus, Elias Gustedt, Jens Mcconnell, Ross M. |
| Description | We give a simple recursive algorithm for modular decomposition of undirected graphs that runs in O(n+ma(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. Key components of the algorithm are variations of a procedure for finding a depth-first forest on the complement of a directed graph G in O(n+m) time. This is surprising, given that it takes Ω(n²) time to compute the complement explicitly. |
| File Format | |
| Language | English |
| Publisher Date | 1997-01-01 |
| Publisher Institution | EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS |
| Access Restriction | Open |
| Subject Keyword | Practical Modular Decomposition Data Structure Trick Depth-first Forest Simple Recursive Algorithm Directed Graph Previous Algorithm Undirected Graph Modular Decomposition Key Component Theoretical Use |
| Content Type | Text |
| Resource Type | Article |
