DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.710

The Minimum Bisection in the Planted Bisection Model

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

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract

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_-) <(p_+) independently. The planted bisection model has been used extensively to benchmark graph partitioning algorithms. If (p_+)=2(d_+)/n and (p_-)=2(d_-)/n for numbers 0 <= (d_-) <(d_+) that remain fixed as n tends to infinity, then with high probability the "planted" bisection (the one used to construct the graph) will not be a minimum bisection. In this paper we derive an asymptotic formula for the minimum bisection width under the assumption that (d_+)-(d_-) > c * sqrt((d_+)ln(d_+)) for a certain constant c>0.

Cite as

Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch. The Minimum Bisection in the Planted Bisection Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 710-725, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX-RANDOM.2015.710,
  author =	{Coja-Oghlan, Amin and Cooley, Oliver and Kang, Mihyun and Skubch, Kathrin},
  title =	{{The Minimum Bisection in the Planted Bisection Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{710--725},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.710},
  URN =		{urn:nbn:de:0030-drops-53315},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.710},
  annote =	{Keywords: Random graphs, minimum bisection, planted bisection, belief propagation.}
}

Search Results

Documents authored by Skubch, Kathrin

The Minimum Bisection in the Planted Bisection Model

Abstract

Cite as

Thanks for your feedback!

Could not send message