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: https://drops.dagstuhl.de/opus/volltexte/2018/8552/
Manoussakis, George
An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs
| pdf-format: |
|
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 | |
| Seminar: | 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) | |
| Issue date: | 2018 | |
| Date of publication: | 02.03.2018 |
