Parameter testing in bounded degree graphs of subexponential growth

DOI10.1002/RSA.20308zbMATH Open1222.05240arXiv0711.2800OpenAlexW3083068705MaRDI QIDQ3055893FDOQ3055893

Gábor Elek

Publication date: 10 November 2010

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

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.

Full work available at URL: https://arxiv.org/abs/0711.2800

zbMATH Keywords

graphsequencesparameter testingmeasurable equivalence relations

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• Title not available (Why is that?)
• Approximate Schreier decorations and approximate Kőnig's line coloring theorem
• Controllability, matching ratio and graph convergence
• Finite graphs and amenability
• An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
• 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
• Every minor-closed property of sparse graphs is testable
• Non-standard limits of graphs and some orbit equivalence invariants
• Title not available (Why is that?)

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)