Improved Approximation Algorithms for Tree Alignment.
Lusheng WangDan GusfieldPublished in: CPM (1996)
Keyphrases
- approximation algorithms
- np hard
- minimum cost
- special case
- vertex cover
- facility location problem
- worst case
- randomized algorithms
- primal dual
- network design problem
- spanning tree
- set cover
- open shop
- np hardness
- approximation ratio
- constant factor
- dynamic time warping
- polynomial time approximation
- tree structure
- precedence constraints
- disjoint paths