Search Results

Documents authored by Manoussakis, George

Document
DOI: 10.4230/LIPIcs.IPEC.2025.22
Efficient Enumeration of k-Plexes and k-Defective Cliques

Authors: Mohamed Jiddou and George Manoussakis

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We investigate the enumeration of dense subgraphs under two well-known relaxations of cliques: k-plexes and k-defective cliques. Our main contribution is a family of algorithms with improved worst-case and output-sensitive complexities, driven by a decomposition technique based on graph degeneracy. We first propose a worst-case output-size near-optimal algorithm to enumerate all maximal k-plexes of size at least 2k-1, achieving a total time complexity of 𝒪(n(dk)³ 2^d Δ^k), where d is the degeneracy and Δ the maximum degree of the input graph. We then refine this result to obtain a fixed-parameter tractable output-sensitive algorithm with complexity 𝒪(α f(k) p(dΔ)), where α is the number of solutions, f(k) is an arbitrary function of k, and p is a polynomial. We then extend this framework to the enumeration of k-defective cliques and also show a linear-time O(n) algorithm for the enumeration of 2-plexes for graphs with bounded degeneracy. To the best of our knowledge, these complexities are competitive with or better than the current state of the art.
Cite as

Mohamed Jiddou and George Manoussakis. Efficient Enumeration of k-Plexes and k-Defective Cliques. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jiddou_et_al:LIPIcs.IPEC.2025.22,
  author =	{Jiddou, Mohamed and Manoussakis, George},
  title =	{{Efficient Enumeration of k-Plexes and k-Defective Cliques}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.22},
  URN =		{urn:nbn:de:0030-drops-251545},
  doi =		{10.4230/LIPIcs.IPEC.2025.22},
  annote =	{Keywords: Parameterized complexity, enumeration algorithms, maximal cliques enumeration}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.27
An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs

Authors: George Manoussakis

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

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.
Cite as

George Manoussakis. An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 27:1-27:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{manoussakis:LIPIcs.IPEC.2017.27,
  author =	{Manoussakis, George},
  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 =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.27},
  URN =		{urn:nbn:de:0030-drops-85529},
  doi =		{10.4230/LIPIcs.IPEC.2017.27},
  annote =	{Keywords: enumeration algorithms, maximal cliques, k-degenerate graphs}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.11
Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3

Authors: Johanne Cohen, Khaled Maâmra, George Manoussakis, and Laurence Pilard

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
We present the first polynomial self-stabilizing algorithm for finding a (2/3)-approximation of a maximum matching in a general graph. The previous best known algorithm has been presented by Manne et al. and has a sub-exponential time complexity under the distributed adversarial daemon. Our new algorithm is an adaptation of the Manne et al. algorithm and works under the same daemon, but with a time complexity in O(n^3) moves. Moreover, our algorithm only needs one more boolean variable than the previous one, thus as in the Manne et al. algorithm, it only requires a constant amount of memory space (three identifiers and two booleans per node).
Cite as

Johanne Cohen, Khaled Maâmra, George Manoussakis, and Laurence Pilard. Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.OPODIS.2016.11,
  author =	{Cohen, Johanne and Ma\^{a}mra, Khaled and Manoussakis, George and Pilard, Laurence},
  title =	{{Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.11},
  URN =		{urn:nbn:de:0030-drops-70808},
  doi =		{10.4230/LIPIcs.OPODIS.2016.11},
  annote =	{Keywords: Self-Stabilization, Distributed Algorithm, Fault Tolerance, Matching}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact