Approximation Algorithms for Some Optimum Communication Spanning Tree Problems.
Bang Ye WuKun-Mao ChaoChuan Yi TangPublished in: ISAAC (1998)
Keyphrases
- approximation algorithms
- minimum cost
- spanning tree
- vertex cover
- approximation schemes
- undirected graph
- np hard
- randomized algorithms
- exact algorithms
- worst case
- special case
- np hardness
- network design problem
- constant factor approximation
- optimization problems
- minimum spanning tree
- primal dual
- minimum weight
- constant factor
- set cover
- search algorithm
- greedy algorithm
- upper bound
- lower bound