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

Graph Partitioning and Planted Partitions

Mikael Onsjö (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Göteborg : Chalmers University of Technology, 2008. - 51 s.
[Licentiatavhandling]

Graph partitioning is the problem of splitting a graph into two or more partitions of fixed sizes while minimizing the number of edges that are “cut”. This is an important problem with a wide range of applications in fields such as VLSI design, parallel processing, bioinformatics, data mining etc. The planted partition model is a commonly used scheme that defines a certain distribution of graphs; a “planted” partition is used in a way that is likely to make it the unique optimal answer to the partitioning problem. Studying graph partitioning on the planted partition model yields a convenient way of describing the efficiency of an algorithm, i.e. by how often it finds the planted partition. For instance, it is known that if the difference between edge probabilities inside and outside partitions p − r = ­(ln n/n) then the planted partition is the unique optimal answer to the partitioning problem with high probability. We present an algorithm that finds the planted partition with high probability if p − r = ­(n−1/2 ln n). This conveniently describes how well the algorithm works and can often with relative ease be compared to similar results for other algorithms. In this thesis we present two papers. The first paper introduces a simple algorithm with results as mentioned above. In the second paper we discuss the intimately related “inference problem” of finding the planted partition, rather than a solution optimal to the normal graph partitioning problem, as well as similar cases for some other combinatorial problems. Defining and studying a class of such problems is an interesting and open problem to the research community.

Nyckelord: graphs, graph partitioning, graph bisection, clustering, planted partition, algorithms



Denna post skapades 2008-02-20.
CPL Pubid: 68394

 

Institutioner (Chalmers)

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

Ämnesområden

Datalogi

Chalmers infrastruktur

Relaterade publikationer

Inkluderade delarbeten:


A Simple Message Passing Algorithm for Graph Partitioning


Finding Most Likely Solutions


Examination

Datum: 2008-03-26
Tid: 10:00
Lokal: Sal EA, EDIT-huset, Rännvägen 4, Chalmers University of Technology.
Opponent: Prof. Pekka Orponen, Dept. of Information and Computer Science, Helsinki University of Technology TKK, Finland.

Ingår i serie

Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University