Worst-Case Minimum Rectilinear Steiner Trees in All Dimensions.
Timothy Law SnyderPublished in: Discret. Comput. Geom. (1992)
Keyphrases
- steiner tree
- worst case
- minimum spanning tree
- constant factor
- lower bound
- upper bound
- np hard
- facility location
- shortest path
- spanning tree
- linear programming relaxation
- approximation algorithms
- minimum cost
- optimal solution
- greedy algorithm
- network flow
- optimization problems
- special case
- computational complexity
- neural network