scientific article; zbMATH DE number 7053340

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.

Mathematics Subject Classification ID

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: