Approximation algorithms for 2-Peripathetic Salesman Problem with edge weights 1 and 2.
Yury GlazkovAlexey BaburinEdward GimadiFederico Della CroceVangelis Th. PaschosPublished in: Electron. Notes Discret. Math. (2006)
Keyphrases
- approximation algorithms
- edge weights
- undirected graph
- weighted graph
- spanning tree
- minimum cost
- bipartite graph
- np hard
- special case
- shortest path
- directed graph
- vertex cover
- worst case
- minimum weight
- minimum spanning tree
- superpixels
- directed acyclic graph
- approximation ratio
- random walk
- constant factor
- triangle inequality
- geodesic distance