# Neighbourhood Evaluation Criteria for Vertex Cover Problem

Source: [Neighbourhood Evaluation Criteria for Vertex Cover Problem](<https://www.sota2.com/research/paper/68fa678e1e209131cea16f3d>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T22:17:13.228Z

Authors: Kaustubh K Joshi

Published: 2020-05-07T05:30:01.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2005.05065>)

[PDF](<https://arxiv.org/pdf/2005.05065.pdf>)
