Approximation to the Minimum Cost Edge Installation Problem.
Ehab MorsyHiroshi NagamochiPublished in: IEICE Trans. Fundam. Electron. Commun. Comput. Sci. (2010)
Keyphrases
- minimum cost
- approximation algorithms
- undirected graph
- approximation ratio
- np hard
- network flow
- spanning tree
- network flow problem
- network simplex algorithm
- edge detection
- special case
- worst case
- capacity constraints
- constant factor
- edit operations
- weighted graph
- knapsack problem
- network design problem
- approximation guarantees
- optimal solution