Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
Text
WRAP_Coja-Oghlan_Quasi_randomness.pdf - Published Version

Download (530Kb) | Preview
Official URL: http://dx.doi.org/10.1137/070709529

Request Changes to record.

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:
DateEvent
2010Published
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us