Efficient Heuristic Algorithms for unweighted minimum vertex cover problem

Barzegaran, Vida; Torabi, Zeinab; Kianian, Sahar

doi:10.48308/jicse.2023.103538

Efficient Heuristic Algorithms for unweighted minimum vertex cover problem

Document Type : Original Article

Authors

vida Barzegaran ¹

Zeinab Torabi ¹

Sahar Kianian ²

¹ Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran.

² Faculty of Computer Engineering, Shahid Rajaee Teacher Training, Tehran, Iran.

https://doi.org/10.48308/jicse.2023.103538

Abstract

Covering all edges in a graph with a small set of vertices is one of the most fundamental graph problems which is called the minimum vertex cover problem. In the literature different strategies have been employed to find near-optimal minimum vertex cover set in different kinds of graphs.
In this work, two efficient algorithms (i.e., MAxA and MAxAR) are introduced to find the minimum vertex cover set in any unweighted undirected graph. The proposed construction algorithms have two main steps in each iteration which explore neighborhoods of minimum degree vertices to find and select appropriate vertices for the cover set. Until all of the edges are removed or selected in the algorithms, these two steps are performed iteratively. The proposed algorithms have been implemented on DIMACS, BHOSLIB, and other benchmarks where experimental results show that the proposed algorithms outperform other relevant methods in terms of time and cardinality of vertex cover set.

Keywords

NP problem

Minimum vertex cover

Heuristic algorithm