Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-085 | 5th August 2005 00:00

#### Homomorphisms in Graph Property Testing - A Survey

TR05-085
Authors: Asaf Shapira, Noga Alon
Publication: 9th August 2005 16:00
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