The Library
Quasi-randomness and algorithmic regularity for graphs with general degree distributions
Tools
Alon, Noga, Coja-Oghlan, Amin, Hàn, Hiêp, Kang, Mihyun, Rödl, Vojtěch and Schacht, Mathias (2010) Quasi-randomness and algorithmic regularity for graphs with general degree distributions. SIAM Journal on Computing, Vol.39 (No.6). pp. 2336-2362. doi:10.1137/070709529 ISSN 0097-5397.
|
Text
WRAP_Coja-Oghlan_Quasi_randomness.pdf - Published Version Download (530Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/070709529
Abstract
We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to express how much a given graph “resembles” a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we introduce a concept of regularity that takes into account vertex weights, and show that if $G=(V,E)$ satisfies a certain boundedness condition, then $G$ admits a regular partition. In addition, building on the work of Alon and Naor [Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, ACM, New York, 2004, pp. 72–80], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph $G$ in polynomial time. As an application, we present a polynomial time approximation scheme for MAX CUT on (sparse) graphs without “dense spots.”
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Random graphs, Partitions (Mathematics) | ||||
Journal or Publication Title: | SIAM Journal on Computing | ||||
Publisher: | Society for Industrial and Applied Mathematics | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Vol.39 | ||||
Number: | No.6 | ||||
Page Range: | pp. 2336-2362 | ||||
DOI: | 10.1137/070709529 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Date of first compliant deposit: | 2 January 2016 | ||||
Date of first compliant Open Access: | 2 January 2016 | ||||
Funder: | European Research Council (ERC), Universiṭat Tel-Aviv. Hermann Minkowski Minerva Center for Geometry, Deutsche Forschungsgemeinschaft (DFG), National Science Foundation (U.S.) (NSF), German-Israeli Foundation for Scientific Research and Development, Israel Science Foundation (ISF) | ||||
Grant number: | CO 646 (DFG), PR 296/7- 3 (DFG), KA 2748/2-1 (DFG), DMS 0300529 (NSF), DMS 0800070 (NSF), SCHA 1263/1- 1 (DFG), 889/05 (GIF) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year