Local Graph Partitions for Approximation and Testing

DOI10.1109/FOCS.2009.77MaRDI QIDQ5171159zbMATH OpenOpenAlexFDO

Authors Avinatan Hassidim, Jonathan Kelner, Huy N. Nguyen, 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Cited in

(42)

• Constructing near spanning trees with few local inspections
• Limits of locally-globally convergent graph sequences
• Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
• An efficient partitioning oracle for bounded-treewidth graphs
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• Finite graphs and amenability
• Approximately counting triangles in sublinear time
• Testing Eulerianity and connectivity in directed sparse graphs
• Planar graphs: random walks and bipartiteness testing
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Intervention efficient algorithms for approximate learning of causal graphs
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• Pliability and approximating Max-CSPs
• The subgraph testing model
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• On the tree-width of even-hole-free graphs
• Introduction to testing graph properties
• New techniques and tighter bounds for local computation algorithms
• Taming vagueness: the philosophy of network science
• Property testing of planarity in the \textsf{CONGEST} model
• Faster property testers in a variation of the bounded degree model
• Introduction to testing graph properties
• Infinite dimensional representations of finite dimensional algebras and amenability
• Local-vs-global combinatorics
• Sublinear time estimation of degree distribution moments: the arboricity connection
• 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
• Locally computing edge orientations
• Faster Property Testers in a Variation of the Bounded Degree Model
• Can we locally compute sparse connected subgraphs?
• Testing outerplanarity of bounded degree graphs
• Sublinear graph approximation algorithms
• On approximating the number of k-cliques in sublinear time
• Spanning adjacency oracles in sublinear time
• Local algorithms for sparse spanning graphs
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Every minor-closed property of sparse graphs is testable
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• Hyperfinite graphings and combinatorial optimization

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

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