The Library
Partitioning random graphs with general degree distributions
Tools
Tools
Tools
Coja-Oghlan, Amin and Lanka, André (2008) Partitioning random graphs with general degree distributions. In: Ausiello, Giorgio and Karhumäki, Juhani and Mauri, Giancarlo and Ong, Luke, (eds.) Fifth Ifip International Conference On Theoretical Computer Science – Tcs 2008. Boston: Springer, pp. 127-141. ISBN 9780387096797
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-0-387-09680-3_9
Abstract
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 Erd˝s-Rényi model Gn,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.
| Item Type: | Book Item | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
| Journal or Publication Title: | Fifth Ifip International Conference On Theoretical Computer Science – Tcs 2008 | ||||
| Publisher: | Springer | ||||
| Place of Publication: | Boston | ||||
| ISBN: | 9780387096797 | ||||
| ISSN: | 1571-5736 | ||||
| Book Title: | Fifth Ifip International Conference On Theoretical Computer Science – Tcs 2008 | ||||
| Editor: | Ausiello, Giorgio and Karhumäki, Juhani and Mauri, Giancarlo and Ong, Luke | ||||
| Official Date: | 2008 | ||||
| Dates: |
|
||||
| Volume: | Vol.273 | ||||
| Page Range: | pp. 127-141 | ||||
| DOI: | 10.1007/978-0-387-09680-3_9 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
