The Library
Testing expansion in bounded-degree graphs
Tools
Tools
Tools
Czumaj, Artur and Sohler, Christian (2010) Testing expansion in bounded-degree graphs. In: Meeting on Combinatorics and Probability, Mathemat Res Inst, Oberwolfach, Germany, April 26-May 02, 2009. Published in: Combinatorics, Probability and Computing, Vol.19 (No.Special Issue 5-6). pp. 693-709. doi:10.1017/S096354831000012X ISSN 0963-5483.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1017/S096354831000012X
Abstract
We consider the problem of testing expansion in hounded-degree graphs. We focus on the notion of vertex expansion: an a-expander is a graph G = (V, E) in which every subset U subset of V of at most vertical bar V vertical bar/2 vertices has a neighbourhood of size at least alpha . vertical bar U vertical bar. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time (O) over tilde(root n). We prove that the property-testing algorithm proposed by Goldreich and Ron with appropriately set parameters accepts every alpha*-expander with probability at least 2/3 and rejects every graph that is epsilon-far from any alpha*-expander with probability at least 2/3, where alpha* = Theta(alpha(2)/d(2) log(n/epsilon)) and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d(2) root n log (n/epsilon)/alpha(2)epsilon(3)).
| Item Type: | Conference Item (UNSPECIFIED) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | Combinatorics, Probability and Computing | ||||
| Publisher: | Cambridge University Press | ||||
| ISSN: | 0963-5483 | ||||
| Official Date: | September 2010 | ||||
| Dates: |
|
||||
| Volume: | Vol.19 | ||||
| Number: | No.Special Issue 5-6 | ||||
| Number of Pages: | 17 | ||||
| Page Range: | pp. 693-709 | ||||
| DOI: | 10.1017/S096354831000012X | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Title of Event: | Meeting on Combinatorics and Probability | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Mathemat Res Inst, Oberwolfach, Germany | ||||
| Date(s) of Event: | April 26-May 02, 2009 |
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 |
