David Eppstein - Publications

• Listing all maximal cliques in sparse graphs in near-optimal time.
  D. Eppstein, M. Löffler, and D. Strash.
  arXiv:1006.5440.
  Workshop on Exact Algorithms for NP-Hard Problems, Dagstuhl, Germany, 2010.
  Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Lecture Notes in Comp. Sci. 6506, 2010, pp. 403-414, Springer-Verlag.
  

  We describe an algorithm for finding all maximal cliques in a graph, in time O(dn3^d/3) where n is the number of vertices and d is the degeneracy of the graph, a standard measure of its sparsity. This time bound matches the worst-case output size for these parameters. The algorithm modifies the Bron-Kerbosch algorithm for maximal cliques by ordering the vertices by degree in the outer recursive call of the algorithm.

Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.