Citation
Bela Bollobas. "Max Cut for random graphs with a planted partition". Combinatorics, Probability and Computing, 13(4-5), 2003.

Abstract
We give an algorithm that, with high probability, recovers a planted k-partition in a random graph, where edges within vertex classes occur with probability p and edges between vertex classes occur with probability . The algorithm can handle vertex classes of different sizes and, for fixed k, runs in linear time. We also give variants of the algorithm for partitioning matrices and hypergraphs.

Electronic downloads

• http://dx.doi.org/10.1017/S0963548304006303

• HTML

  Bela Bollobas. <a
  href="http://chess.eecs.berkeley.edu/pubs/727.html"
  >Max Cut for random graphs with a planted
  partition</a>, <i>Combinatorics, Probability and
  Computing</i>, 13(4-5),  2003.

• Plain text

  Bela Bollobas. "Max Cut for random graphs with a
  planted partition". <i>Combinatorics, Probability
  and Computing</i>, 13(4-5),  2003.

• BibTeX

  @article{Bollobas03_MaxCutForRandomGraphsWithPlantedPartition,
      author = {Bela Bollobas},
      title = {Max Cut for random graphs with a planted partition},
      journal = {Combinatorics, Probability and Computing},
      volume = {13},
      number = {4-5},
      year = {2003},
      abstract = {We give an algorithm that, with high probability,
                recovers a planted k-partition in a random graph,
                where edges within vertex classes occur with
                probability p and edges between vertex classes
                occur with probability . The algorithm can handle
                vertex classes of different sizes and, for fixed
                k, runs in linear time. We also give variants of
                the algorithm for partitioning matrices and
                hypergraphs.},
      URL = {http://chess.eecs.berkeley.edu/pubs/727.html}
  }
  

Posted by Christopher Brooks on 4 Nov 2010.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.