Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-085 | 5th August 2005 00:00

Homomorphisms in Graph Property Testing - A Survey

RSS-Feed




TR05-085
Authors: Asaf Shapira, Noga Alon
Publication: 9th August 2005 16:00
Downloads: 2946
Keywords: 


Abstract:

Property-testers are fast randomized algorithms for distinguishing
between graphs (and other combinatorial structures) satisfying a
certain property, from those that are far from satisfying it. In
many cases one can design property-testers whose running time is in
fact {\em independent} of the size of the input. In this paper we
survey some recent results on testing graph properties. A common
thread in all the results surveyed is that they rely heavily on the
simple yet useful notion of graph homomorphism. We mainly focus
on the combinatorial aspects of property-testing.



ISSN 1433-8092 | Imprint