Introduction to Testing Graph Properties
From MaRDI portal
Publication:4933365
DOI10.1007/978-3-642-16367-8_7zbMath1309.68219OpenAlexW3023402925MaRDI QIDQ4933365
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_7
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving, Unnamed Item, Unnamed Item, Testing the \((s,t)\) connectivity of graphs and digraphs, Testable and untestable classes of first-order formulae, Introduction to Testing Graph Properties, On the Complexity of Sampling Vertices Uniformly from a Graph, Dynamic graph stream algorithms in \(o(n)\) space, How long it takes for an ordinary node with an ordinary ID to output?, Multiscale Matrix Sampling and Sublinear-Time PageRank Computation
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
- Introduction to Testing Graph Properties
- 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
