Shrink: An Efficient Construction Algorithm for Minimum Vertex Cover Problem
Publication Type
Original research
Authors
Fulltext
Download

The minimum vertex cover (VC) problem is to find a minimum number of vertices in an undirected graph such that every edge in the graph is incident to at least one of these vertices. This problem is a classical NP-hard combinatorial optimization problem with applications in a wide range of areas. Hence, there is a need to develop approximate algorithms to find a small VC in a reasonable time. This paper presents a new construction algorithm for the minimum VC problem. Extensive experiments on benchmark graphs show that the proposed algorithm is extremely competitive and complementary to existing construction algorithms for minimum VC problem.

Journal
Title
Information Sciences Letters
Publisher
Natural Sciences Publishing
Publisher Country
United States of America
Indexing
Scopus
Impact Factor
None
Publication Type
Both (Printed and Online)
Volume
10
Year
2021
Pages
255-261