Local Graph Partitions for Approximation and Testing

DOI10.1109/FOCS.2009.77zbMath1292.68126OpenAlexW2153822379MaRDI QIDQ5171159

Jonathan A. Kelner, Huy N. Nguyen, Avinatan Hassidim, Krzysztof Onak

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.77

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (35)

Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs ⋮ New techniques and tighter bounds for local computation algorithms ⋮ Planarity can be verified by an approximate proof labeling scheme in constant-time ⋮ Can we locally compute sparse connected subgraphs? ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ Infinite dimensional representations of finite dimensional algebras and amenability ⋮ Approximately Counting Triangles in Sublinear Time ⋮ Faster Property Testers in a Variation of the Bounded Degree Model ⋮ Unnamed Item ⋮ Local-vs-global combinatorics ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Constructing near spanning trees with few local inspections ⋮ Introduction to Testing Graph Properties ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Hyperfinite graphings and combinatorial optimization ⋮ Limits of locally-globally convergent graph sequences ⋮ On the tree-width of even-hole-free graphs ⋮ Testing outerplanarity of bounded degree graphs ⋮ Every minor-closed property of sparse graphs is testable ⋮ Finite graphs and amenability ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ Sublinear Graph Approximation Algorithms ⋮ Unnamed Item ⋮ Local algorithms for sparse spanning graphs ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs ⋮ An Efficient Partitioning Oracle for Bounded-Treewidth Graphs ⋮ Introduction to Testing Graph Properties ⋮ 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 ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ Planar graphs: Random walks and bipartiteness testing ⋮ Unnamed Item ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian

This page was built for publication: Local Graph Partitions for Approximation and Testing