Testing expansion in bounded-degree graphs
Czumaj, Artur and Sohler, Christian (2007) Testing expansion in bounded-degree graphs. In: 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, OCT 20-23, 2007. Published in: 48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS pp. 570-578.Full text not available from this repository.
We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an cc-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 neighborhood 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 (2000) with appropriately set parameters accepts every alpha-expander with probability at least 2/3 and rejects every graph that is epsilon-far from an 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
T Technology > TK Electrical engineering. Electronics Nuclear engineering
|Divisions:||Faculty of Science > Computer Science|
|Journal or Publication Title:||48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS|
|Publisher:||IEEE COMPUTER SOC|
|Number of Pages:||9|
|Page Range:||pp. 570-578|
|Title of Event:||48th Annual IEEE Symposium on Foundations of Computer Science|
|Location of Event:||Providence, RI|
|Date(s) of Event:||OCT 20-23, 2007|
Actions (login required)