A fast heuristic for the minimum weight vertex cover problem.
Satoshi ShimizuKazuaki YamaguchiToshiki SaitohSumio MasudaPublished in: ICIS (2016)
Keyphrases
- vertex cover
- minimum weight
- planar graphs
- greedy heuristic
- approximation algorithms
- np hard
- minimum spanning tree
- bipartite graph
- randomized algorithm
- weighted graph
- spanning tree
- greedy algorithm
- optimal solution
- lower bound
- knapsack problem
- tree patterns
- special case
- optimality criterion
- precedence constraints
- simulated annealing
- combinatorial optimization
- bin packing
- dynamic programming
- evolutionary algorithm
- polynomial time approximation