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

DOI10.1016/S0020-0190(97)00175-0MaRDI QIDQ293142zbMATH OpenOpenAlexFDO

Authors Yang Dai, Kazuo Iwano, 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

randomized algorithmsminimum cutminimum range cutprobabilistic analysis

Mathematics Subject Classification ID

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

Recommendations

• A new approach to the minimum cut problem
• Minimum Cuts of Simple Graphs in Almost Always Linear Time
• Asymptotically Optimal Linear Algorithm for the Minimum k-Cut in a Random Graph
• scientific article; zbMATH DE number 437525
• Random sampling in cut, flow, and network design problems

Cites work

• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 3902655 (Why is no real title available?)
• 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
• Efficient algorithms for minimum range cut problems
• The solution of some random NP-hard problems in polynomial expected time

Cited in

(3)

• On the structure of contractible edges in \(k\)-connected partial \(k\)-trees
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• Improved bounds and algorithms for graph cuts and network reliability

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293142)