Introduction to Testing Graph Properties
From MaRDI portal
Publication:3088198
DOI10.1007/978-3-642-22670-0_32zbMath1343.68299OpenAlexW2113337364MaRDI QIDQ3088198
Publication date: 19 August 2011
Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_32
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Testing Lipschitz functions on hypergrid domains, Testing list \(H\)-homomorphisms, Erasures versus errors in local decoding and property testing, Non-interactive proofs of proximity, A Brief Introduction to Property Testing, Randomness and Computation, Contemplations on Testing Graph Properties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for sampling algorithms for estimating the average
- A separation theorem in property testing
- Testing the expansion of a graph
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Self-testing/correcting with applications to numerical problems
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- A sublinear bipartiteness tester for bounded degree graphs
- Tolerant property testing and distance approximation
- Testing k-colorability
- A combinatorial characterization of the testable graph properties
- Property testing and its connection to learning and approximation
- Approximating average parameters of graphs
- Every monotone graph property is testable
- Testing versus estimation of graph properties
- Testing triangle-freeness in general graphs
- Testing graph isomorphism
- Distance Approximation in Bounded-Degree and General Sparse Graphs
- On the Benefits of Adaptivity in Property Testing of Dense Graphs
- The complexity of promise problems with applications to public-key cryptography
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Three theorems regarding testing graph properties
- Testing the diameter of graphs
- Testing properties of directed graphs: acyclicity and connectivity*
- Tight Bounds for Testing Bipartiteness in General Graphs
- Testing subgraphs in large graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- MAX-CUT has a randomized approximation scheme in dense graphs
- A Brief Introduction to Property Testing
- Hierarchy Theorems for Property Testing
- Local Graph Partitions for Approximation and Testing
- lgorithmic and Analysis Techniques in Property Testing
- Approximate Hypergraph Partitioning and Applications
- Computational Complexity
- An Expansion Tester for Bounded Degree Graphs
- Testing subgraphs in directed graphs
- Efficient testing of large graphs
- Property testing in bounded degree graphs
