The minimum bisection in the planted bisection model

A. Coja-Oghlan, O. Cooley, M. Kang, K. Skubch

    Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


    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.
    Original languageEnglish
    Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
    Place of PublicationSchloss Dagstuhl
    PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
    ISBN (Print)978-3-939897-89-7
    Publication statusPublished - 2015

    Publication series

    NameLeibniz International Proceedings in Informatics

    Fields of Expertise

    • Information, Communication & Computing

    Treatment code (Nähere Zuordnung)

    • Basic - Fundamental (Grundlagenforschung)

    Cite this