Approximation algorithms for minimum-cost augmentation to k-edge-connect a multigraph.

Toshimasa Watanabe Toshiya Mashima Satoshi Taoka

Published in: ISCAS (1993)

Keyphrases

approximation algorithms
minimum cost
disjoint paths
undirected graph
np hard
special case
network flow
worst case
spanning tree
primal dual
network flow problem
approximation ratio
network design problem
randomized algorithms
vertex cover
capacity constraints
upper bound
combinatorial auctions
optimal solution