Accession Number : ADA536611


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


Descriptive Note : Conference paper


Corporate Author : CALIFORNIA UNIV IRVINE SCHOOL OF INFORMATION AND COMPUTER SCIENCE


Personal Author(s) : Eppstein, David ; Loffler, Maarten ; Strash, Darren


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a536611.pdf


Report Date : Jan 2011


Pagination or Media Count : 15


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{exp 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 greater than or equal to d+3) is (n-d)3{exp d/}3. Therefore, our algorithm matches the Theta(d(n-d)3{exp d/3}) worst-case output size of the problem whenever n-d = Omega(n).


Descriptors :   *NUMERICAL METHODS AND PROCEDURES , *ALGORITHMS , TIME DOMAIN , NUMERICAL ANALYSIS , OPTIMIZATION , SYMPOSIA , GRAPHS


Subject Categories : Numerical Mathematics
      Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE