文章基本信息

标题：The Minimum Bisection in the Planted Bisection Model
本地全文：下载
作者：Amin Coja-Oghlan ; Oliver Cooley ; Mihyun Kang 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：40
页码：710-725
DOI：10.4230/LIPIcs.APPROX-RANDOM.2015.710
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In the planted bisection model a random graph G(n,p_+,p_-) with n vertices is created by partitioning the vertices randomly into two classes of equal size (up to plus or minus 1). Any two vertices that belong to the same class are linked by an edge with probability p_+ and any two that belong to different classes with probability (p_-) c * sqrt((d_+)ln(d_+)) for a certain constant c>0.
关键词：Random graphs; minimum bisection; planted bisection; belief propagation.