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

DOI10.1016/S0020-0190(97)00175-0zbMATH Open1339.68310OpenAlexW2018130031MaRDI QIDQ293142FDOQ293142

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

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

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)

Cites Work

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient algorithms for minimum range cut problems

Cited In (2)

• On the structure of contractible edges in \(k\)-connected partial \(k\)-trees
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model

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)