The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality.
Hans-Joachim BöckenhauerKarin FreiermuthJuraj HromkovicTobias MömkeAndreas SprockBjörn SteffenPublished in: CIAC (2010)
Keyphrases
- triangle inequality
- steiner tree
- similarity search
- nearest neighbor
- quadratic assignment problem
- distance function
- minimum spanning tree
- distance measure
- metric space
- shortest path
- nearest neighbor search
- facility location
- pre computed
- distance metric
- similarity function
- edge weights
- edit distance
- dissimilarity measure
- linear programming relaxation
- cost model
- similarity queries
- similarity measure
- lower bound
- spanning tree
- tabu search