Neighbourhood Evaluation Criteria for Vertex Cover Problem
This work addresses a classic NP-hard graph problem, but appears incremental as it builds on existing heuristic approaches without claiming major breakthroughs.
The paper tackles the Minimum Vertex Cover problem by proposing a heuristic algorithm that selects vertices based on degree count, neighborhood influence, and independent set enabling count, achieving unspecified performance improvements.
Neighbourhood Evaluation Criteria is a heuristical approximate algorithm that attempts to solve the Minimum Vertex Cover. degree count is kept in check for each vertex and the highest count based vertex is included in our cover set. In the case of multiple equivalent vertices, the one with the lowest neighbourhood influence is selected. In the case of still existing multiple equivalent vertices, the one with the lowest remaining active vertex count (the highest Independent Set enabling count) is selected as a tie-breaker.