Show that the family of bridge sets, BW (R), is the set of bases of a matroid
for any tree (T, W) and any R ⊆ T .
(Goemans et al. [2012])
Find a combinatorial 2-factor approximation algorithm for the SURVIVABLE
NETWORK DESIGN PROBLEM with rij = k for all i, j (i.e. the MINIMUM
WEIGHT k-EDGE-CONNECTED SUBGRAPH PROBLEM).
Hint: Replace each edge by a pair of oppositely directed edges (with the same
weight) and apply either Exercise 26 of Chapter 13 or Theorem 6.18 directly.
(Khuller and Vishkin [1994])
Note: For more results for similar problems, see Khuller and Raghavachari
[1996], Gabow [2005], Jothi, Raghavachari and Varadarajan [2003], and Gabow
et al. [2009].