MIT
65
Problem Statement
lGiven vertices,
and cost cvw to buy and edge
from v to w, find minimum cost purchase
that creates a graph with desired connectivity properties
lExample: minimum
cost k-connected graph.
lGenerally NP-hard
lRecent
approximation algorithms [GW],[JV]