Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Quasi-randomness and algorithmic regularity for graphs with general degree distributions
Authors: Noga Alon ; Amin Coja-Oghlan ; Hiep Han ; Mihyun Kang ; Vojtech Rodl ; Mathias Schacht
Date:Jul 2007
Publication Title:Proc. ICALP 2007
Publication Type:Conference Paper Publication Status:Published
Volume No:4596 Page Nos:789-800
DOI:10.1007/978-3-540-73420-8_68 ISBN/ISSN:978-3-540-73419-2
We deal with two very related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to measure 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 present a novel concept of regularity that takes into account the graph's degree distribution, 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, we provide an algorithm that computes a regular partition of a given (possibly sparse) graph G in polynomial time.
Links To Paper
No links available
Bibtex format
author = { Noga Alon and Amin Coja-Oghlan and Hiep Han and Mihyun Kang and Vojtech Rodl and Mathias Schacht },
title = {Quasi-randomness and algorithmic regularity for graphs with general degree distributions},
book title = {Proc. ICALP 2007},
publisher = {Springer},
year = 2007,
month = {Jul},
volume = {4596},
pages = {789-800},
doi = {10.1007/978-3-540-73420-8_68},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh