The Library
Quasi-randomness and algorithmic regularity for graphs with general degree distributions
Tools
Tools
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
|
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 > 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 | ||||
| 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
