Efficient and practical modular decomposition
| dc.contributor.author | Dahlhaus, Elias | |
| dc.contributor.author | Gustedt, Jens | |
| dc.contributor.author | McConnell, Ross | |
| dc.date.accessioned | 2021-12-17T10:05:33Z | |
| dc.date.available | 2021-12-17T10:05:33Z | |
| dc.date.issued | 1996 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15494 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14267 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | algorithm | en |
| dc.subject.other | modular decomposition | en |
| dc.subject.other | computation | en |
| dc.subject.other | graphs | en |
| dc.title | Efficient and practical modular decomposition | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 1996, 524 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |