Fast constructive and improvement heuristics for edge clique covering
Marcos Okamura Rodrigues · Discrete Optimization · 2021
The edge clique covering problem consists in covering the edges of a graph using the minimum number of cliques. The problem is NP-hard and even state-of-the-art heuristic methods may have prohibitive runtime or obtain low quality solutions. This paper proposes fast and better constructive and improvement heuristics for the problem. Computational experiments show the proposed heuristics can find better solutions in few seconds for most instances. Tests were run on edge clique covering, DIMACS and BHOSLIB instances.