Property testing in bounded degree graphs
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- A sublinear-time approximation scheme for bin packing
- The Bradley-Terry condition is \(L_1\)-testable
- Dynamic graph stream algorithms in \(o(n)\) space
- Non-interactive proofs of proximity
- Measuring instance difficulty for combinatorial optimization problems
- Testing metric properties
- Fast approximate probabilistically checkable proofs
- On the strength of comparisons in property testing
- Comparing the strength of query types in property testing: the case of \(k\)-colorability
- A sublinear bipartiteness tester for bounded degree graphs
- On the tree-width of even-hole-free graphs
- Planarity can be verified by an approximate proof labeling scheme in constant-time
- Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
- Estimating the number of connected components in sublinear time
- Hierarchy theorems for testing properties in size-oblivious query complexity
- Local algorithms for sparse spanning graphs
- On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
- Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time
- Testing the supermodular-cut condition
- Infinite dimensional representations of finite dimensional algebras and amenability
- Property testing on \(k\)-vertex-connectivity of graphs
- Testing of matrix-poset properties
- Combinatorial PCPs with short proofs
- scientific article; zbMATH DE number 1670872 (Why is no real title available?)
- Two-sided error proximity oblivious testing
- Constant-time algorithms for sparsity matroids
- Local reconstructors and tolerant testers for connectivity and diameter
- Finding cycles and trees in sublinear time
- On testable properties in bounded degree graphs
- Testing cluster structure of graphs
- Parameter testing in bounded degree graphs of subexponential growth
- Quantum property testing for bounded-degree graphs
- An efficient partitioning oracle for bounded-treewidth graphs
- On testing expansion in bounded-degree graphs
- On the average-case complexity of property testing
- A Brief Introduction to Property Testing
- Introduction to testing graph properties
- Contemplations on Testing Graph Properties
- Another motivation for reducing the randomness complexity of algorithms
- Property testing and its connection to learning and approximation
- On the query complexity of testing orientations for being Eulerian
- Property testing for bounded degree databases
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- Homomorphisms in graph property testing
- Testing list H-homomorphisms
- Property Testing on k-Vertex-Connectivity of Graphs
- On the Query Complexity of Testing Orientations for Being Eulerian
- Testing outerplanarity of bounded degree graphs
- Distance Approximation in Bounded-Degree and General Sparse Graphs
- Testing Graph Isomorphism
- Relational Properties Expressible with One Universal Quantifier Are Testable
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Spanders: distributed spanning expanders
- scientific article; zbMATH DE number 1241385 (Why is no real title available?)
- Testing the \((s,t)\) connectivity of graphs and digraphs
- Hierarchy theorems for property testing
- Testable and untestable classes of first-order formulae
- Three theorems regarding testing graph properties
- Testing connectivity of faulty networks in sublinear time
- scientific article; zbMATH DE number 1559556 (Why is no real title available?)
- Testing the diameter of graphs
- scientific article; zbMATH DE number 1792102 (Why is no real title available?)
- Approximately counting triangles in sublinear time
- scientific article; zbMATH DE number 6846422 (Why is no real title available?)
- Testing \(k\)-edge-connectivity of digraphs
- Testing Expansion in Bounded-Degree Graphs
- Testing for forbidden posets in ordered rooted forests
- A brief introduction to property testing
- Sublinear-time Algorithms
- Introduction to testing graph properties
- Sublinear graph approximation algorithms
- Invariance in property testing
- Comparing the strength of query types in property testing: the case of testing \(k\)-colorability
- Hierarchy theorems for property testing
- Algorithmic Aspects of Property Testing in the Dense Graphs Model
- Testing Euclidean Spanners
- scientific article; zbMATH DE number 1418268 (Why is no real title available?)
- Testing outerplanarity of bounded degree graphs
- Zero-knowledge proofs of proximity
- On the probe complexity of local computation algorithms
- A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
- Lower bounds for approximating graph parameters via communication complexity
- Quantum walk sampling by growing seed sets
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- The subgraph testing model
- On the Effect of the Proximity Parameter on Property Testers
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Flexible Models for Testing Graph Properties
- Testable bounded degree graph properties are random order streamable
- Testing forest-isomorphism in the adjacency list model
- Algorithmic and analysis techniques in property testing
- Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
- Planar graphs: random walks and bipartiteness testing
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Testing convexity properties of tree colorings
- The subgraph testing model
- An explicit construction of graphs of bounded degree that are far from being Hamiltonian
- Erasure-resilient sublinear-time graph algorithms
- scientific article; zbMATH DE number 7650132 (Why is no real title available?)
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
This page was built for publication: Property testing in bounded degree graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5957578)
