Property testing in bounded degree graphs
From MaRDI portal
Publication:5957578
DOI10.1007/s00453-001-0078-7zbMath0990.68103OpenAlexW1980816908MaRDI QIDQ5957578
Publication date: 7 March 2002
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-001-0078-7
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Testing metric properties, Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving, Fast approximate probabilistically checkable proofs, Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, Testing graphs against an unknown distribution, On the strength of comparisons in property testing, Planarity can be verified by an approximate proof labeling scheme in constant-time, Testing list \(H\)-homomorphisms, Finding cycles and trees in sublinear time, Infinite dimensional representations of finite dimensional algebras and amenability, On the benefits of adaptivity in property testing of dense graphs, Property Testing for Bounded Degree Databases, 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, Spanders: distributed spanning expanders, Flexible Models for Testing Graph Properties, Approximately Counting Triangles in Sublinear Time, Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs, Faster Property Testers in a Variation of the Bounded Degree Model, Unnamed Item, Unnamed Item, Unnamed Item, The Bradley-Terry condition is \(L_1\)-testable, Testing the \((s,t)\) connectivity of graphs and digraphs, Comparing the strength of query types in property testing: the case of \(k\)-colorability, Hierarchy theorems for property testing, Unnamed Item, Testable and untestable classes of first-order formulae, Unnamed Item, Algorithmic Aspects of Property Testing in the Dense Graphs Model, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, Testing Eulerianity and connectivity in directed sparse graphs, Distribution-free connectivity testing for sparse graphs, Testing \(k\)-edge-connectivity of digraphs, On the Query Complexity of Testing Orientations for Being Eulerian, Zero-Knowledge Proofs of Proximity, Testing Euclidean Spanners, Hierarchy Theorems for Property Testing, The power and limitations of uniform samples in testing properties of figures, Testing of matrix-poset properties, On the tree-width of even-hole-free graphs, Testing outerplanarity of bounded degree graphs, Dynamic graph stream algorithms in \(o(n)\) space, Non-interactive proofs of proximity, Testing Expansion in Bounded-Degree Graphs, Distributed Testing of Graph Isomorphism in the CONGEST Model., Estimating the number of connected components in sublinear time, Every minor-closed property of sparse graphs is testable, Testing the expansion of a graph, Measuring instance difficulty for combinatorial optimization problems, TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS, Testing convexity properties of tree colorings, Unnamed Item, Sublinear-time Algorithms, Sublinear Graph Approximation Algorithms, Invariance in Property Testing, Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability, Unnamed Item, Fast distributed algorithms for testing graph properties, Hierarchy theorems for testing properties in size-oblivious query complexity, Two-sided error proximity oblivious testing, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Proximity Oblivious Testing and the Role of Invariances, Proximity Oblivious Testing and the Role of Invariances, Local algorithms for sparse spanning graphs, On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs, Quantum Property Testing for Bounded-Degree Graphs, An Efficient Partitioning Oracle for Bounded-Treewidth 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, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Every Set in P Is Strongly Testable Under a Suitable Encoding, Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time, Relational Properties Expressible with One Universal Quantifier Are Testable, A sublinear-time approximation scheme for bin packing, Planar graphs: Random walks and bipartiteness testing, An explicit construction of graphs of bounded degree that are far from being Hamiltonian, Testing the supermodular-cut condition, Combinatorial PCPs with short proofs
