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

DOI10.1016/J.TCS.2007.04.040MaRDI QIDQ995573zbMATH OpenOpenAlexFDO

Authors Michal Parnas, Dana Ron

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

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

Cited in

(33)

• Constructing near spanning trees with few local inspections
• An efficient partitioning oracle for bounded-treewidth graphs
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• On the probe complexity of local computation algorithms
• Minimum entropy combinatorial optimization problems
• Minimum entropy combinatorial optimization problems
• Dynamic approximate vertex cover and maximum matching
• Approximately counting triangles in sublinear time
• The program of the mini-workshop
• Space-efficient local computation algorithms
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• 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
• Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
• Almost stable matchings by truncating the Gale-Shapley algorithm
• 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
• Can we locally compute sparse connected subgraphs?
• Sublinear graph approximation algorithms
• Fully dynamic maximal matching in \(O(\log n)\) update time
• Improved dynamic colouring of sparse graphs
• 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
• Local algorithms for sparse spanning graphs
• Round compression for parallel matching algorithms
• Distributed discovery of large near-cliques
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• On constant time approximation of parameters of bounded degree graphs
• Local computation algorithms for graphs of non-constant degrees

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)