Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms

DOI10.1016/J.TCS.2007.04.040zbMATH Open1188.68358OpenAlexW1980155175MaRDI QIDQ995573FDOQ995573

Dana Ron, Michal Parnas

Publication date: 3 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.040

zbMATH Keywords

distributed algorithmsminimum vertex coversublinear approximation algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)

Cites Work

• Title not available (Why is that?)
• Data Streams: Algorithms and Applications
• Title not available (Why is that?)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• On the hardness of approximating minimum vertex cover
• Robust Characterizations of Polynomials with Applications to Program Testing
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Tight Bounds for Testing Bipartiteness in General Graphs
• Estimating the weight of metric minimum spanning trees in sublinear-time
• The price of being near-sighted
• Approximating Average Parameters of Graphs
• Sublinear time approximate clustering
• On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
• Distance Approximation in Bounded-Degree and General Sparse Graphs
• Automata, Languages and Programming

Cited In (34)

• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Fast distributed algorithms for testing graph properties
• Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information
• Minimum entropy combinatorial optimization problems
• Minimum entropy combinatorial optimization problems
• Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
• Dynamic approximate vertex cover and maximum matching
• The program of the mini-workshop
• An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
• On Approximating the Number of $k$-Cliques in Sublinear Time
• Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
• A sublinear-time approximation scheme for bin packing
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• New techniques and tighter bounds for local computation algorithms
• Best of two local models: centralized local and distributed local algorithms
• Almost stable matchings by truncating the Gale-Shapley algorithm
• On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Title not available (Why is that?)
• Can we locally compute sparse connected subgraphs?
• Sublinear graph approximation algorithms
• Improved dynamic colouring of sparse graphs
• Sublinear algorithms for \((1.5+\epsilon)\)-approximate matching
• Sublinear time algorithms and complexity of approximate maximum matching
• Approximately Counting Triangles in Sublinear Time
• Round Compression for Parallel Matching Algorithms
• Local algorithms for sparse spanning graphs
• Distributed discovery of large near-cliques
• Title not available (Why is that?)
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• On constant time approximation of parameters of bounded degree graphs
• Constructing near spanning trees with few local inspections
• Local computation algorithms for graphs of non-constant degrees
• Title not available (Why is that?)

This page was built for publication: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q995573)