A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
From MaRDI portal
Publication:5743463
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
Cites work
- scientific article; zbMATH DE number 5485551 (Why is no real title available?)
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating average parameters of graphs
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Counting stars and other small subgraphs in sublinear time
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Every property of hyperfinite graphs is testable
- Local Graph Partitions for Approximation and Testing
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
- Parameter testing in bounded degree graphs of subexponential growth
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
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
- scientific article; zbMATH DE number 5631194 (Why is no real title available?)
- Approximately counting triangles in sublinear time
- Best of two local models: centralized local and distributed local algorithms
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- 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
- Distance Approximation in Bounded-Degree and General Sparse Graphs
- scientific article; zbMATH DE number 7561379 (Why is no real title available?)
- 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)
