Name
Abstract | ||
|---|---|---|
We present here a new algorithm linear in time and space complexity for Modular Decomposition. This algorithm relies on structural properties of prime graphs (see theorems 7, and 8), on properties of modules (see property 1 and corollary 1) but also on the cograph recognition algorithm [CPS85]. Our algorithm builds and explores the decomposition tree of any undirected graph in a depth-first search way. As a by-product we show that a vertex-splitting operation is really a central tool for modular decomposition algorithms. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1007/BFb0017474 | CAAP |
Keywords | Field | DocType |
clans,vertex-splitting,autonomous subsets,graph decomposition trees,substitution,new linear algorithm,modules,modular decomposition,cographs,prime graphs,: graphs,cotrees.,space complexity,depth first search | Prime (order theory),Discrete mathematics,Graph,Modular decomposition,Spacetime,Tree decomposition,Matrix decomposition,Cograph,Corollary,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-57879-X | 101 | 7.13 |
References | Authors | |
11 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alain Cournier | 1 | 281 | 22.07 |
| Michel Habib | 2 | 240 | 24.86 |