Performance comparison of approximation algorithms for the minimum weight vertex cover problem.
Satoshi TaokaToshimasa WatanabePublished in: ISCAS (2012)
Keyphrases
- vertex cover
- approximation algorithms
- minimum weight
- planar graphs
- np hard
- special case
- greedy heuristic
- minimum cost
- spanning tree
- bipartite graph
- worst case
- approximation ratio
- weighted graph
- precedence constraints
- partial order
- undirected graph
- log likelihood
- constant factor
- tree patterns
- minimum spanning tree
- polynomial time approximation