Hill-climbing finds random planted bisections (Q2768397)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Hill-climbing finds random planted bisections |
scientific article; zbMATH DE number 1699315
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Hill-climbing finds random planted bisections |
scientific article; zbMATH DE number 1699315 |
Statements
5 July 2003
0 references
random block models
0 references
minimum balanced bisection of graphs
0 references
algorithm performance
0 references
Hill-climbing finds random planted bisections (English)
0 references
A random graph model with a planted bisection consists of two disjoint Bernoulli blocks of order \(n\) having edge probability \(p\) within the blocks and edge probability \(q\) between the blocks. Separation conditions on the parameters \(p\) and \(q\) are given that guarantee that the bisection can be found by some simple hill-climbing algorithms.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].
0 references
