Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs.
Ashkan AazamiJoseph CheriyanKrishnam Raju JampaniPublished in: APPROX-RANDOM (2009)
Keyphrases
- approximation algorithms
- steiner tree
- planar graphs
- vertex cover
- undirected graph
- np hard
- worst case
- packing problem
- special case
- minimum spanning tree
- minimum cost
- facility location
- shortest path
- computational complexity
- integer programming
- np complete
- linear programming relaxation
- optimal solution
- primal dual
- weighted graph
- approximate inference
- bayesian networks
- branch and bound algorithm
- greedy algorithm
- linear programming
- binary variables
- minimum weight
- scheduling problem
- evolutionary algorithm