Algorithmic Aspects of Property Testing in the Dense Graphs Model
From MaRDI portal
Publication:4933381
DOI10.1007/978-3-642-16367-8_23zbMath1309.68222MaRDI QIDQ4933381
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68W20: Randomized algorithms
Related Items
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