next up previous
Next: The Graph Clustering Problem Up: Sabbatical at MIT (1996-1998) Previous: Collision-Free Hashing from Lattice

Property Testing in Bounded Degree Graphs

This work initiates the study of testing graph properties in the bounded-length incidence lists model. In particular, it presence testing algorithms for connectivity and k-connectivity, and lower bounds on the query complexity of testing bipartiteness and graph expansion.


Comments: Authored by O. Goldreich and D. Ron. Appeared in



Oded Goldreich
2003-07-30