Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time

Details Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time

2010-06-28

arxiv.org/abs/1006.5440v1

Computer Science

Data Structures and Algorithms

13 pages, 3 figures

Scientific paper

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\ge 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)$.

Affiliated with

Also associated with

No associations

Rating

Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-618932