Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Partitioning random graphs with general degree distributions
Authors: Amin Coja-Oghlan ; Andre Lanka
Date:Mar 2008
Publication Title:Fifth IFIP International Conference on Theoretical Computer Science - TCS 2008
Publisher:Springer Boston
Publication Type:Conference Paper Publication Status:Published
Volume No:273 Page Nos:127-141
DOI:10.1007/978-0-387-09680-3_9 ISBN/ISSN:978-0-387-09679-7
We consider the problem of recovering a planted partition (e.g., a small bisection or a large cut) from a random graph. During the last 30 years many algorithms for this problem have been developed that work provably well on models resembling the Erdos-Renyi model G(n,m). Since in these random graph models edges are distributed very uniformly, the recent theory of large networks provides convincing evidence that real-world networks, albeit looking random in some sense, cannot sensibly be described by these models. Therefore, a variety of new types of random graphs have been introduced. One of the most popular of these new models is characterized by a prescribed expected degree sequence. We study a natural variant of this model that features a planted partition, the main result being that there is a polynomial time algorithm for recovering (a large share of) the planted partition efficiently. In contrast to prior work, the algorithm's input only consists of the graph, i.e., no further parameters of the distribution (such as the expected degree sequence) are required.
Links To Paper
No links available
Bibtex format
author = { Amin Coja-Oghlan and Andre Lanka },
title = {Partitioning random graphs with general degree distributions},
book title = {Fifth IFIP International Conference on Theoretical Computer Science - TCS 2008},
publisher = {Springer Boston},
year = 2008,
month = {Mar},
volume = {273},
pages = {127-141},
doi = {10.1007/978-0-387-09680-3_9},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh