Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess

The problem of finding a minimum vertex cover (MinVC) in a graph is a well known NP-hard combinatorial optimization problem of great importance in theory and practice. Due to its NP-hardness, there has been much interest in developing heuristic algorithms for finding a small vertex cover in reasonab... View More