Algorithmic Aspects of Property Testing in the Dense Graphs Model

DOI10.1137/090749621zbMath1234.68137OpenAlexW2808268686MaRDI QIDQ5892636

Oded Goldreich, Dana Ron

Publication date: 29 July 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090749621

zbMATH Keywords

graph propertiesproperty testingadaptivity versus nonadaptivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

Testing Odd-Cycle-Freeness in Boolean Functions ⋮ An adaptivity hierarchy theorem for property testing ⋮ Two-sided error proximity oblivious testing ⋮ Unnamed Item

This page was built for publication: Algorithmic Aspects of Property Testing in the Dense Graphs Model