Name
Abstract | ||
|---|---|---|
The degeneracy of an n-vertex graph G is the smallest number d such that every subgraph of G contains a vertex of degree at most d. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron-Kerbosch algorithm and show that it runs in time O(dn3(d/3)). We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an n-vertex graph with degeneracy d (when d is a multiple of 3 and n >= d + 3) is (n - d)3(d/3). Therefore, our algorithm matches the Theta(d(n - d)3(d/3)) worst-case output size of the problem whenever n - d = Omega(n). |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-17517-6_36 | ALGORITHMS AND COMPUTATION, PT I |
Keywords | DocType | Volume |
sparse graphs,d-degenerate graphs,maximal clique listing algorithms,Bron-Kerbosch algorithm,fixed-parameter tractability | Journal | 6506 |
ISSN | Citations | PageRank |
0302-9743 | 76 | 2.40 |
References | Authors | |
30 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Eppstein | 1 | 4897 | 533.94 |
| Maarten Löffler | 2 | 551 | 62.87 |
| Darren Strash | 3 | 238 | 17.72 |