All reports by Author Asaf Nachmias:

__
TR07-118
| 27th November 2007
__

Asaf Nachmias, Asaf Shapira#### Testing the Expansion of a Graph

Asaf Nachmias, Asaf Shapira

We study the problem of testing the expansion of

graphs with bounded degree d in sublinear time. A graph is said to

be an \alpha-expander if every vertex set U \subset V of size at

most |V|/2 has a neighborhood of size at least \alpha|U|.

We show that the algorithm ... more >>>