The Library
Graph partitioning via adaptive spectral techniques
Tools
Coja-Oghlan, Amin (2010) Graph partitioning via adaptive spectral techniques. Combinatorics, Probability and Computing, Vol.19 (No.2). pp. 227-284. doi:10.1017/S0963548309990514 ISSN 0963-5483.
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.1017/S0963548309990514
Abstract
In this paper we study the use of spectral techniques for graph partitioning. Let G = (V, E) be a graph whose vertex set has a ‘latent’ partition V1,. . ., Vk. Moreover, consider a ‘density matrix’ = (vw)v, swV such that, for v Vi and w Vj, the entry vw is the fraction of all possible Vi−Vj-edges that are actually present in G. We show that on input (G, k) the partition V1,. . ., Vk can (very nearly) be recovered in polynomial time via spectral methods, provided that the following holds: approximates the adjacency matrix of G in the operator norm, for vertices v Vi, w Vj ≠ Vi the corresponding column vectors v, w are separated, and G is sufficiently ‘regular’ with respect to the matrix . This result in particular applies to sparse graphs with bounded average degree as n = #V → ∞, and it has various consequences on partitioning random graphs.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Combinatorics, Probability and Computing | ||||
Publisher: | Cambridge University Press | ||||
ISSN: | 0963-5483 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Vol.19 | ||||
Number: | No.2 | ||||
Page Range: | pp. 227-284 | ||||
DOI: | 10.1017/S0963548309990514 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |