### Skapa referens, olika format (klipp och klistra)

**Harvard**

Onsjö, M. (2008) *Graph Partitioning and Planted Partitions*. Göteborg : Chalmers University of Technology (Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, nr: ).

** BibTeX **

@book{

Onsjö2008,

author={Onsjö, Mikael},

title={Graph Partitioning and Planted Partitions},

abstract={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.},

publisher={Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers), Chalmers tekniska högskola,},

place={Göteborg},

year={2008},

series={Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, no: },

keywords={graphs, graph partitioning, graph bisection, clustering, planted partition, algorithms},

note={51},

}

** RefWorks **

RT Dissertation/Thesis

SR Print

ID 68394

A1 Onsjö, Mikael

T1 Graph Partitioning and Planted Partitions

YR 2008

AB 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.

PB Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers), Chalmers tekniska högskola,

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

LA eng

OL 30