Algorithmic Aspects of Property Testing in the Dense Graphs Model

DOI10.1007/978-3-642-16367-8_23zbMath1309.68222OpenAlexW3089932723MaRDI QIDQ4933381

Dana Ron, Oded Goldreich

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_23

zbMATH Keywords

graph propertiesadaptivity vs. non-adaptivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Related Items

Testing Juntas: A Brief Survey, Fast distributed algorithms for testing graph properties, Inflatable Graph Properties and Natural Property Tests

Cites Work

• Unnamed Item
• Lower bounds for sampling algorithms for estimating the average
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• On the strength of comparisons in property testing
• A combinatorial characterization of the testable graph properties
• Property testing and its connection to learning and approximation
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• Three theorems regarding testing graph properties
• Robust Characterizations of Polynomials with Applications to Program Testing
• On proximity oblivious testing
• lgorithmic and Analysis Techniques in Property Testing
• Some 3CNF Properties Are Hard to Test
• Testing Graph Blow-Up
• Efficient testing of large graphs
• Property testing in bounded degree graphs