A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems

DOI10.1016/S0020-0190(97)00175-0zbMath1339.68310OpenAlexW2018130031MaRDI QIDQ293142

Kazuo Iwano, Yang Dai, Naoki Katoh

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097001750?np=y

zbMATH Keywords

minimum cutprobabilistic analysisrandomized algorithmsminimum range cut

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (1)

On the structure of contractible edges in \(k\)-connected partial \(k\)-trees

Cites Work

• Unnamed Item
• Unnamed Item
• A matroid approach to finding edge connectivity and packing arborescences
• A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
• The solution of some random NP-hard problems in polynomial expected time
• Efficient algorithms for minimum range cut problems

This page was built for publication: A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems