SCIENCE@home

Minimum cuts in near-linear time

David R Karger

Published 1998 in JACM

ABSTRACT

We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized (Monte Carlo) algorithm that finds a minimum cut in an <italic>m</italic>-edge, <italic>n</italic>-vertex graph with high probability in <italic>O</italic>(m log<supscrpt>3</supscrpt> <italic>n</italic>) time. We also give a simpler randomized algorithm that finds <italic>all</italic> minimum cuts with high probability in O(<italic>m</italic> log<supscrpt>3</subscrpt> <italic>n</italic>) time. This variant has an optimal <italic>RNC</italic> parallelization. Both variants improve on the previous best time bound of <italic>O<italic>(<italic>n<italic><supscrpt>2</supscrpt> log<supscrpt>3</supscrpt> <italic>n<italic>). Other applications of the tree-packing approach are new, nearly tight bounds on the number of <italic>near-minimum</italic> cuts a graph may have and a new data structure for representing them in a space-efficient manner.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-39 of 39 references · Page 1 of 1

CITED BY

Showing 1-100 of 362 citing papers · Page 1 of 4

1234
Next