Three theorems regarding testing graph properties

DOI10.1002/rsa.10078zbMath1048.68062WikidataQ105583190 ScholiaQ105583190MaRDI QIDQ4417002

Oded Goldreich, Luca Trevisan

Publication date: 6 August 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10078

zbMATH Keywords

graph properties; property testing; NP; monotone properties

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

68W20: Randomized algorithms

Related Items

Algorithmic Aspects of Property Testing in the Dense Graphs Model, Introduction to Testing Graph Properties, Hierarchy Theorems for Property Testing, Testing subgraphs in directed graphs, Testing permutation properties through subpermutations, On the benefits of adaptivity in property testing of dense graphs, \(\omega\)-regular languages are testable with a constant number of queries, Distribution-free connectivity testing for sparse graphs, A separation theorem in property testing, Indistinguishability and First-Order Logic

Cites Work

• Sampling algorithms