Approximating the distance to properties in bounded-degree and general sparse graphs

DOI10.1145/1497290.1497298zbMath1446.68197OpenAlexW2081449822MaRDI QIDQ4962788

Dana Ron, Sharon Marko

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1497290.1497298

zbMATH Keywords

graph propertiesproperty testingsublinear approximation algorithmsdistance approximation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20) Vertex degrees (05C07)

Related Items (12)

Approximating the distance to monotonicity of Boolean functions ⋮ Approximately Counting Triangles in Sublinear Time ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Constructing near spanning trees with few local inspections ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Sublinear Graph Approximation Algorithms ⋮ Unnamed Item ⋮ Local algorithms for sparse spanning graphs ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ An Efficient Partitioning Oracle for Bounded-Treewidth Graphs ⋮ Planar graphs: Random walks and bipartiteness testing ⋮ Unnamed Item

This page was built for publication: Approximating the distance to properties in bounded-degree and general sparse graphs