The minimum bisection in the planted bisection model

DOI10.4086/TOC.2017.V013A008MaRDI QIDQ5368899zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Kathrin Skubch

Publication date 11 October 2017

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2017.v013a008

zbMATH Keywords

belief propagationminimum bisectionplanted bisectionrandom graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• The minimum bisection in the planted bisection model
• Algorithms for graph partitioning on the planted partition model
• scientific article; zbMATH DE number 1418276
• Bisecting sparse random graphs
• A spectral heuristic for bisecting random graphs

Cited in

(8)

• Algorithms for graph partitioning on the planted partition model
• A spectral heuristic for bisecting random graphs
• The peculiar phase structure of random graph bisection
• scientific article; zbMATH DE number 1418276 (Why is no real title available?)
• The minimum bisection in the planted bisection model
• A Simple Message Passing Algorithm for Graph Partitioning Problems
• On the minimum bisection of random 3-regular graphs
• Bad local minima exist in the stochastic block model

This page was built for publication: The minimum bisection in the planted bisection model

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