License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.27
URN: urn:nbn:de:0030-drops-85529
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8552/
Go to the corresponding LIPIcs Volume Portal

Manoussakis, George

An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs

pdf-format:
LIPIcs-IPEC-2017-27.pdf (0.4 MB)

Abstract

The degeneracy of a graph G is the smallest integer k such that every subgraph of G contains a vertex of degree at most k. Given an n-order k-degenerate graph G, we present an algorithm for enumerating all its maximal cliques. Assuming that c is the number of maximal cliques of G, our algorithm has setup time O(n(k^2+s(k+1))) and enumeration time cO((k+1)f(k+1)) where s(k+1) (resp. f(k+1)) is the preprocessing time (resp. enumeration time) for maximal clique enumeration in a general (k+1)-order graph. This is the first output sensitive algorithm whose enumeration time depends only on the degeneracy of the graph.

BibTeX - Entry

@InProceedings{manoussakis:LIPIcs:2018:8552,
  author =	{George Manoussakis},
  title =	{{An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{27:1--27:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8552},
  URN =		{urn:nbn:de:0030-drops-85529},
  doi =		{10.4230/LIPIcs.IPEC.2017.27},
  annote =	{Keywords: enumeration algorithms, maximal cliques, k-degenerate graphs}
}

Keywords: enumeration algorithms, maximal cliques, k-degenerate graphs
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI