ABSTRACT
Two paths in a graph are internally disjoint if no internal node of one of the paths belongs to the other. A graph is k-connected if it contains k pairwise internally disjoint paths from every node to any other node. We survey approximation algorithms for the k-Connected Subgraph problem, formally defined as follows.
