b'@techreport{,'b'\nTITLE = {Approximating minimum size 1,2-connected networks},\nAUTHOR = {Krysta, Piotr},\nLANGUAGE = {eng},\nURL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2001-1-001},\nNUMBER = {MPI-I-2001-1-001},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {2001},\nDATE = {2001},\nABSTRACT = {The problem of finding the minimum size 2-connected subgraph is a classical problem in network design. It is known to be NP-hard even on cubic planar graphs and Max-SNP hard. We study the generalization of this problem, where requirements of 1 or 2 edge or vertex disjoint paths are specified between every pair of vertices, and the aim is to find a minimum subgraph satisfying these requirements. For both problems we give $3/2$-approximation algorithms. This improves on the straightforward $2$-approximation algorithms for these problems, and generalizes earlier results for 2-connectivity. We also give analyses of the classical local optimization heuristics for these two network design problems.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'