On the benefits of adaptivity in property testing of dense graphs

DOI10.1007/s00453-008-9237-4zbMath1202.68279OpenAlexW2295491750MaRDI QIDQ603911

Dana Ron, Mira Gonen

Publication date: 8 November 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9237-4

zbMATH Keywords

adaptivityproperty testingbipartiteness

Mathematics Subject Classification ID

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

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spot-checkers
• On the strength of comparisons in property testing
• A sublinear bipartiteness tester for bounded degree graphs
• Testing k-colorability
• A combinatorial characterization of the testable graph properties
• Property testing and its connection to learning and approximation
• Every monotone graph property is testable
• Poisson approximation for large deviations
• Three theorems regarding testing graph properties
• Tight Bounds for Testing Bipartiteness in General Graphs
• Testing graphs for colorability properties*
• Testing subgraphs in large graphs
• Abstract Combinatorial Programs and Efficient Property Testers
• Testing versus Estimation of Graph Properties
• Some 3CNF Properties Are Hard to Test
• Efficient testing of large graphs
• Property testing in bounded degree graphs