A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
From MaRDI portal
Publication:5743463
zbMATH Open1422.68310arXiv1110.1079MaRDI QIDQ5743463FDOQ5743463
Authors: Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld 
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1110.1079
Recommendations
- Distance Approximation in Bounded-Degree and General Sparse Graphs
- Approximating the distance to properties in bounded-degree and general sparse graphs
- A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
- Sublinear graph approximation algorithms
- Approximately counting triangles in sublinear time
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Approximating average parameters of graphs
- Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
- Title not available (Why is that?)
- Every property of hyperfinite graphs is testable
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Local Graph Partitions for Approximation and Testing
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Parameter testing in bounded degree graphs of subexponential growth
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Counting stars and other small subgraphs in sublinear time
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
Cited In (23)
- Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Approximation of Self-stabilizing Vertex Cover Less Than 2
- Title not available (Why is that?)
- Approximately counting triangles in sublinear time
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- Best of two local models: centralized local and distributed local algorithms
- Approximating the distance to monotonicity of Boolean functions
- On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
- Sublinear time estimation of degree distribution moments: the arboricity connection
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
- Sublinear time approximation of the cost of a metric \(k\)-nearest neighbor graph
- Sublinear graph approximation algorithms
- Sublinear algorithms for \((1.5+\epsilon)\)-approximate matching
- Sublinear time algorithms and complexity of approximate maximum matching
- On approximating the number of \(k\)-cliques in sublinear time
- Title not available (Why is that?)
- Distance Approximation in Bounded-Degree and General Sparse Graphs
- Almost optimal query algorithm for hitting set using a subset query
- Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- A simple LP-free approximation algorithm for the minimum weight vertex cover problem
- Local computation algorithms for graphs of non-constant degrees
This page was built for publication: A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743463)
