| k-connected subgraph |
|
|
|
|
|
|
|
|
|
|
| l | Fractional
solution is k-connected |
||||||||
| l | So every cut has
(expected) k edges |
||||||||
| crossing in
rounded solution |
|||||||||
| l | Sampling theorem
says every cut has at |
||||||||
| least k-(k log n)1/2 edges |
|||||||||
| l | Close
approximation for large k |
||||||||
| l | Can often repair:
e.g., get k-connected |
||||||||
| subgraph at cost 1+((log n)/k)1/2 times min |
|||||||||
