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

(45)

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

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)