Approximation Algorithms for Finding a Maximum-Weight Spanning Connected Subgraph with given Vertex Degrees.
Alexey BaburinEdward GimadiPublished in: OR (2004)
Keyphrases
- approximation algorithms
- maximum weight
- np hard
- minimum weight
- undirected graph
- minimum cost
- spanning tree
- bipartite graph
- greedy heuristic
- special case
- worst case
- independent set
- vertex cover
- approximation ratio
- weighted graph
- optimal solution
- linear programming
- set cover
- partial order
- disjoint paths
- lower bound
- connected components
- randomized algorithms
- minimum spanning tree
- constant factor
- computational complexity
- precedence constraints
- edge weights
- tree patterns
- optimization problems
- scheduling problem
- constant factor approximation