1.Previous
3.Next

that runs in worst case time.

The Karger-Stein variant of Karger's algorithm provides a faster randomized algorithm for determining the connectivity, with expected runtime .

A related problem: finding the minimum k-edge-connected spanning subgraph of G (that is: select as few as possible edges in G that your selection is k-edge-connected) is NP-hard for .