Every Property of Hyperfinite Graphs Is Testable
From MaRDI portal
Publication:2848211
DOI10.1137/120890946zbMath1272.05033OpenAlexW2006450313MaRDI QIDQ2848211
Publication date: 25 September 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/120890946
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Extremal combinatorics (05D99)
Related Items (21)
Approximating Bounded Degree Deletion via Matroid Matching ⋮ Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs ⋮ Infinite dimensional representations of finite dimensional algebras and amenability ⋮ Property Testing for Bounded Degree Databases ⋮ Approximating power node-deletion problems ⋮ Testability in group theory ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Faster Property Testers in a Variation of the Bounded Degree Model ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ Unnamed Item ⋮ On the tree-width of even-hole-free graphs ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Convergence theorems for graph sequences ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs ⋮ Planar graphs: Random walks and bipartiteness testing ⋮ Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian
This page was built for publication: Every Property of Hyperfinite Graphs Is Testable
