- Abstract:
- 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
- @InProceedings{EDI-INF-RR-1112,
- 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},
- }
|
