Premium
Algorithms for graph partitioning on the planted partition model
Author(s) -
Condon Anne,
Karp Richard M.
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200103)18:2<116::aid-rsa1001>3.0.co;2-2
Subject(s) - combinatorics , graph partition , partition (number theory) , frequency partition of a graph , mathematics , undirected graph , strength of a graph , graph , random graph , partition problem , discrete mathematics , connectivity , line graph , graph power
The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into two equal‐sized groups so as to minimize the number of edges that cross the partition. The more general graph l ‐partition problem is to partition the nodes of an undirected graph into l equal‐sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear‐time algorithm for the graph l ‐partition problem and we analyze it on a random “planted l ‐partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n / l ; two nodes in the same group are connected by an edge with some probability p , and two nodes in different groups are connected by an edge with some probability r < p . We show that if p − r ≥ n −1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(− n Θ(ε) ). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001