A Metaheuristic Approach to Solving the  Generalized Vertex Cover Problem

Milanović, Marija

Displaying similar documents to “A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem”

Avoiding Unstructured Workflows in Prerequisites Modeling

Boris Milašinović, Krešimir Fertalj (2012)

Computer Science and Information Systems

Similarity:

A comparison of three algorithms for reducing the profile of a sparse matrix

Alain Billionnet, Jean-François Brêteau (1989)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

Edith Hemaspaandra, Jörg Rothe, Holger Spakowski (2006)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of $r$ , where $r$ is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to $NP$ . To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs...