CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A Simple Message Passing Algorithm for Graph Partitioning

Mikael Onsjö (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Osamu Watanabe
Algorithms and Computation 17th International Symposium, ISAAC 2006 Kolkata, India, December 18-20, 2006 Proceedings, Asano, Tetsuo (Ed.) Vol. 4288 (2006), p. 507-516.
[Konferensbidrag, refereegranskat]

Motivated by the belief propagation, we propose a simple and deterministic message passing algorithm for the Graph Bisection problem and related problems. The running time of the main algorithm is linear w.r.t. the number of vertices and edges. For evaluating its average-case correctness, planted solution models are used. For the Graph Bisection problem under the standard planted solution model with probability pa- rameters p and r, we prove that our algorithm yields a planted solution with probability > 1 − δ if p − r = Ω(n−1/2 log(n/δ)).

Nyckelord: Graph Partitioning, Belief Propagation

Denna post skapades 2007-01-11.
CPL Pubid: 25238


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)



Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:

Graph Partitioning and Planted Partitions