Parameter testing in bounded degree graphs of subexponential growth

DOI10.1002/RSA.20308MaRDI QIDQ3055893zbMATH OpenOpenAlexFDO

Authors Gábor Elek

Publication date 10 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.2800, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.315.6731

zbMATH Keywords

graphsequencesparameter testingmeasurable equivalence relations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Parameter testing algorithms are using constant number of queries to estimate the value of a certain parameter of a very large finite graph. It is well-known that graph parameters such as the independence ratio or the edit-distance from 3-colorability are not testable in bounded degree graphs. We prove, however, that these and several other interesting graph parameters are testable in bounded degree graphs of subexponential growth.

Recommendations

• Property testing in bounded degree graphs
• An Expansion Tester for Bounded Degree Graphs
• scientific article; zbMATH DE number 1559556
• Graph limits and parameter testing
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs

Cites work

• scientific article; zbMATH DE number 5485551 (Why is no real title available?)
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• An Invitation to Random Schroedinger operators
• Approximation algorithms for NP-complete problems on planar graphs
• Graph limits and parameter testing
• Hyperfinite graph limits
• Limits of dense graph sequences
• On limits of finite graphs
• Recurrence of distributional limits of finite planar graphs
• Remark on the continuity of the density of states of ergodic finite difference operators
• Some APX-completeness results for cubic graphs
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• Testing versus Estimation of Graph Properties
• \(L^{2}\)-spectral invariants and convergent sequences of finite graphs

Cited in

(15)

• An efficient partitioning oracle for bounded-treewidth graphs
• Parameterized testability
• Approximate Schreier decorations and approximate Kőnig's line coloring theorem
• Finite graphs and amenability
• Controllability, matching ratio and graph convergence
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• The subgraph testing model
• The matroid of a graphing
• Infinite dimensional representations of finite dimensional algebras and amenability
• Borel oracles. An analytical approach to constant-time algorithms
• Testing Expansion in Bounded-Degree Graphs
• Parameterized testability
• Hyper resolution and equality axioms without function substitutions
• Every minor-closed property of sparse graphs is testable
• Non-standard limits of graphs and some orbit equivalence invariants

This page was built for publication: Parameter testing in bounded degree graphs of subexponential growth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055893)