Autor:	Oliver Cooley, Kathrin Skubch, Amin Coja-Oghlan, Mihyun Kang
Rok vydání:	2017
Předmět:	Combinatorics Random graph Class (set theory) Computational Theory and Mathematics Bisection Edge (geometry) Belief propagation Equal size Constant (mathematics) Theoretical Computer Science Mathematics
Zdroj:	Theory of Computing. 13:1-22
ISSN:	1557-2862
DOI:	10.4086/toc.2017.v013a008
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::00f3520df87937b1bc6a760331321445 https://doi.org/10.4086/toc.2017.v013a008 Zobrazit plný text záznamu