Name
Abstract | ||
|---|---|---|
A graph is said to be prime if it has no non-trivial substitution decomposition, or module. This paper introduces a simple but efficient (O(n + m ln n)) algorithm to test the primality of undirected graphs. The fastest previous algorithm is due to Muller and Spinrad [MS89] and requires quadratic time. Our approach can be seen as a common generalization of Spinrad's work on P
4-tree structure and substitution decomposition [Spi89] and Ille's one about the structure of prime graphs [Ill90] (see also Schmerl and Trotter [ST91] which contains similar results). |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1007/3-540-56402-0_49 | WG |
Keywords | Field | DocType |
efficient algorithm,prime graphs.,. undirected graphs,recognize prime undirected graphs,au- tonomous subsets,modules,substitution decomposition,tree structure | Prime (order theory),Discrete mathematics,Graph,Combinatorics,Primality test,Prim's algorithm,Algorithm,Time complexity,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-56402-0 | 21 | 2.53 |
References | Authors | |
8 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alain Cournier | 1 | 281 | 22.07 |
| Michel Habib | 2 | 240 | 24.86 |