A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
From MaRDI portal
(Redirected from 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
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating average parameters of graphs
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- 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
- scientific article; zbMATH DE number 5485551 (Why is no real title available?)
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- 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
(27)- Sublinear-time algorithms for counting star subgraphs via edge sampling
- Best of two local models: centralized local and distributed local algorithms
- Distance Approximation in Bounded-Degree and General Sparse Graphs
- scientific article; zbMATH DE number 5631194 (Why is no real title available?)
- Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
- Approximately counting triangles in sublinear time
- Sublinear graph approximation algorithms
- Sublinear time estimation of degree distribution moments: the arboricity connection
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
- Parameterized query complexity of hitting set using stability of sunflowers
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- On approximating the number of k-cliques in sublinear time
- Local computation algorithms for graphs of non-constant degrees
- Approximation of Self-stabilizing Vertex Cover Less Than 2
- Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
- Approximating the distance to monotonicity of Boolean functions
- On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
- Almost optimal query algorithm for hitting set using a subset query
- Sublinear time approximation of the cost of a metric k-nearest neighbor graph
- Sublinear algorithms for (1.5+)-approximate matching
- Sublinear time algorithms and complexity of approximate maximum matching
- A simple LP-free approximation algorithm for the minimum weight vertex cover problem
- Sublinear algorithms and lower bounds for metric TSP cost estimation
- Non-adaptive edge counting and sampling via bipartite independent set queries
- Dynamic matching with better-than-2 approximation in polylogarithmic update time
- Range counting oracles for geometric problems
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)
