Minimum cuts in near-linear time 论文

2000Journal of the ACM引用 287

Complexity and Algorithms in GraphsComputational Geometry and Mesh GenerationVLSI and FPGA Design Techniques

VLSI and FPGA Design Techniques Complexity and Algorithms in Graphs Computational Geometry and Mesh Generation

作者

摘要

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 m -edge, n -vertex graph with high probability in O (m log 3 n ) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O( m log 3 n ) time. This variant has an optimal RNC parallelization. Both variants improve on the previous best time bound of O ( n 2 log 3 n ). Other applications of the tree-packing approach are new, nearly tight bounds on the number of near-minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.

作者查看全部 (1)

David R. Karger

Minimum cuts in near-linear time 论文

详细信息

摘要

作者查看全部 (1)

相关技术查看全部 (2)

相关事件

相关文章