Skip to main content

Research Repository

Advanced Search

Analysis of an iterated greedy heuristic for vertex clique covering

Chalupa, David; Pospíchal, Jiří

Authors

David Chalupa

Jiří Pospíchal



Abstract

The aim of the vertex clique covering problem (CCP) is to cover the vertices of a graph with as few cliques as possible. We analyse the iterated greedy (IG) algorithm for CCP, which was previously shown to provide strong empirical results for real-world networks. It is demonstrated how the techniques of analysis for randomised search heuristics can be applied to IG, and several practically relevant results are obtained. We show that for triangle-free graphs, IG solves CCP optimally in expected polynomial time. Secondly, we show that IG finds the optimum for CCP in a specific case of sparse random graphs in expected polynomial time with high probability. For Baraba´si-Albert model of scale-free networks, which is a canonical model explaining the growth of social, biological or computer networks, we obtain that IG obtains an asymptotically optimal approximation in polynomial time in expectation. Last but not least, we propose a slightly modified variant of IG, which guarantees expected polynomial-time convergence to the optimum for graphs with non-overlapping triangles.

Citation

Chalupa, D., & Pospíchal, J. (2018). Analysis of an iterated greedy heuristic for vertex clique covering. Computing and Informatics, 37(2), 385-404. https://doi.org/10.4149/cai_2018_2_385

Journal Article Type Article
Acceptance Date Sep 14, 2016
Publication Date Apr 30, 2018
Deposit Date Oct 25, 2016
Publicly Available Date Mar 28, 2024
Journal Computing and informatics
Print ISSN 1335-9150
Electronic ISSN 2585-8807
Peer Reviewed Peer Reviewed
Volume 37
Issue 2
Article Number 385-404
Pages 385-404
DOI https://doi.org/10.4149/cai_2018_2_385
Keywords Vertex clique covering problem; Iterated greedy; Randomised search heuristics; Complex networks; Random graphs
Public URL https://hull-repository.worktribe.com/output/444539
Publisher URL http://www.cai.sk/ojs/index.php/cai/article/view/2018_2_385
Additional Information This is the accepted manuscript of an article published in Computing and informatics, 2018. The version of record is available at the DOI link in this record.

Files





You might also like



Downloadable Citations