Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with hereditary properties:
TR17-058 | 7th April 2017
Noga Alon, Omri Ben-Eliezer, Eldar Fischer

Testing hereditary properties of ordered graphs and matrices

Revisions: 1

We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries.
We also explain how the proof can ... more >>>

ISSN 1433-8092 | Imprint