Next: The Graph Clustering Problem
Up: Sabbatical at MIT (1996-1998)
Previous: Collision-Free Hashing from Lattice
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
- Proc. of the 29th STOC, pages 406-415, 1997.
- Algorithmica, Vol. 32 (2), pages 302-343, 2002.
Oded Goldreich
2003-07-30