The Library
Quasirandomness and algorithmic regularity for graphs with general degree distributions
Tools
Alon, Noga, CojaOghlan, Amin, Hàn, Hiêp, Kang, Mihyun, Rödl, Vojtěch and Schacht, Mathias. (2010) Quasirandomness and algorithmic regularity for graphs with general degree distributions. SIAM Journal on Computing, Vol.39 (No.6). pp. 23362362. ISSN 00975397

Text
WRAP_CojaOghlan_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: quasirandomness and regular partitions. The purpose of the concept of quasirandomness 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 quasirandom graphs. Regarding quasirandomness, 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:  00975397  
Official Date:  2010  
Dates: 


Volume:  Vol.39  
Number:  No.6  
Page Range:  pp. 23362362  
Identification Number:  10.1137/070709529  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Open Access  
Funder:  European Research Council (ERC), Universiṭat TelAviv. Hermann Minkowski Minerva Center for Geometry, Deutsche Forschungsgemeinschaft (DFG), National Science Foundation (U.S.) (NSF), GermanIsraeli Foundation for Scientific Research and Development, Israel Science Foundation (ISF)  
Grant number:  CO 646 (DFG), PR 296/7 3 (DFG), KA 2748/21 (DFG), DMS 0300529 (NSF), DMS 0800070 (NSF), SCHA 1263/1 1 (DFG), 889/05 (GIF)  
References:  [1] R. Albert and A. L. Barab´asi, Statistical mechanics of complex networks, Rev. Modern 

URI:  http://wrap.warwick.ac.uk/id/eprint/3320 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year