Algorithmic Aspects of Property Testing in the Dense Graphs Model

DOI10.1007/978-3-642-16367-8_23MaRDI QIDQ4933381zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Dana Ron

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

adaptivity vs. non-adaptivitygraph properties

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Algorithmic aspects of property testing in the dense graphs model
• scientific article; zbMATH DE number 1792102
• On the benefits of adaptivity in property testing of dense graphs
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• Property testing in bounded degree graphs
• scientific article; zbMATH DE number 1559556
• Testing versus Estimation of Graph Properties

Cites work

• A combinatorial characterization of the testable graph properties, it's all about regularity
• Algorithmic and analysis techniques in property testing
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Efficient testing of large graphs
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• Lower bounds for sampling algorithms for estimating the average
• On proximity oblivious testing
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• On the strength of comparisons in property testing
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Some 3CNF Properties Are Hard to Test
• Testing graph blow-up
• Three theorems regarding testing graph properties

Cited in

(10)

• Comparing the strength of query types in property testing: the case of \(k\)-colorability
• Inflatable graph properties and natural property tests
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• Testing juntas: a brief survey
• Testing versus Estimation of Graph Properties
• Algorithmic aspects of property testing in the dense graphs model
• Testing graph blow-up
• Testing graph blow-up
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• On the benefits of adaptivity in property testing of dense graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933381)