Fast Maximal Cliques Enumeration in Sparse Graphs
- Publication Type:
- Journal Article
- Citation:
- Algorithmica, 2013, 66 (1), pp. 173 - 186
- Issue Date:
- 2013-05-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 2013002445OK.pdf | 501.29 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
In this paper, we consider the problem of generating all maximal cliques in a sparse graph in polynomial delay. Given a graph G=(V,E) with n vertices and m edges, the latest and fastest polynomial delay algorithm for sparse graphs enumerates all maximal cliques in O(δ 4) time delay, where δ is the maximum degree of vertices. However, it requires an O(n×m) preprocessing time. We improve it in two aspects. First, our algorithm does not need preprocessing. Therefore, our algorithm is a truly polynomial delay algorithm. Second, our algorithm enumerates all maximal cliques in O(δ×H 3) time delay, where H is the so called H-value of a graph or equivalently it is the smallest integer satisfying |{vâ̂̂Vâ̂£δ(v)≥H}|≤H given δ(v) as the degree of a vertex. In real-world network data, H usually is a small value and much smaller than δ. © 2012 Springer Science+Business Media, LLC.
Please use this identifier to cite or link to this item: