2026-07-21T23:45:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8552 2024-03-06T10:41:32Z ddc:004 open_access

An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs Manoussakis, George enumeration algorithms maximal cliques k-degenerate graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik George Manoussakis 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.27 urn:nbn:de:0030-drops-85529 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.27 eng https://creativecommons.org/licenses/by/3.0/legalcode