Introduction to Testing Graph Properties
From MaRDI portal
Publication:4933365
DOI10.1007/978-3-642-16367-8_7zbMath1309.68219MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
Introduction to Testing Graph Properties, Testing the \((s,t)\) connectivity of graphs and digraphs, Testable and untestable classes of first-order formulae, Dynamic graph stream algorithms in \(o(n)\) space
Cites Work
- Unnamed Item
- 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
- 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
