loading...
Testing Expansion in Bounded-Degree Graphs
Providence, Rhode Island October 21-October 23
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.3348th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an \alpha - \expander is a graph G = (V; E) in which every subset U \subseteq V of at most \left| V \right|/2 vertices has a neighborhood of size at least \alpha \cdot \left| U \right|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time \mathop O\limits^\~ (\sqrt n ). We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every \alpha - \exp ander with probability at least \frac{2} {3} and rejects every graph that is \in - far from an \alpha * - \exp ander with probability at least \frac{2} {3}, where \alpha * = \Theta (\frac{{\alpha ^2 }} {{d^2 \log (n/ \in )}}) 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(\frac{{d^2 \sqrt n \log (n/ \in )}} {{\alpha ^2 \in ^3 }}).
Citation:
Artur Czumaj, Christian Sohler, "Testing Expansion in Bounded-Degree Graphs," focs, pp.570-578, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.