Czumaj, Artur and Sohler, Christian (2007) Testing expansion in bounded-degree graphs. In: 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, 20-23 Oct 2007. Published in: 48th Annual IEEE Symposium on Foundations of Computer Science, 2007. FOCS '07. pp. 570-578. ISBN 9780769530109. doi:10.1109/FOCS.2007.4389526

PDF 04389526.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (296Kb)

Request Changes to record.

Abstract

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 (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title:	48th Annual IEEE Symposium on Foundations of Computer Science, 2007. FOCS '07.
Publisher:	IEEE
ISBN:	9780769530109
Official Date:	2007
Dates:	Date Event 2007 Published
Number of Pages:	9
Page Range:	pp. 570-578
DOI:	10.1109/FOCS.2007.4389526
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	14 December 2015
Conference Paper Type:	Paper
Title of Event:	48th Annual IEEE Symposium on Foundations of Computer Science
Type of Event:	Other
Location of Event:	Providence, RI
Date(s) of Event:	20-23 Oct 2007
Related URLs:	Organisation

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