scientific article; zbMATH DE number 7053340
From MaRDI portal
Publication:5743463
zbMath1422.68310arXiv1110.1079MaRDI QIDQ5743463
Ronitt Rubinfeld, Krzysztof Onak, Michal Rosen, Dana Ron
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1110.1079
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (14)
Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions ⋮ Approximately Counting Triangles in Sublinear Time ⋮ Almost optimal query algorithm for hitting set using a subset query ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Unnamed Item ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Parameter testing in bounded degree graphs of subexponential growth
- Approximating average parameters of graphs
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Local Graph Partitions for Approximation and Testing
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
- Every property of hyperfinite graphs is testable
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
This page was built for publication:
