Asymptotically Optimal Linear Algorithm for the Minimum k-Cut in a Random Graph

DOI10.1137/0403007zbMath0745.05046OpenAlexW1997556777MaRDI QIDQ4710964

Olivier Goldschmidt, Dorit S. Hochbaum

Publication date: 25 June 1992

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0403007

zbMATH Keywords

random graphlinear algorithm\(k\)-cut problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

This page was built for publication: Asymptotically Optimal Linear Algorithm for the Minimum k-Cut in a Random Graph