Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
From MaRDI portal
Publication:995573
DOI10.1016/j.tcs.2007.04.040zbMath1188.68358OpenAlexW1980155175MaRDI QIDQ995573
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
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)
Related Items
New techniques and tighter bounds for local computation algorithms, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Can we locally compute sparse connected subgraphs?, Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs, On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions, Approximately Counting Triangles in Sublinear Time, Unnamed Item, On Approximating the Number of $k$-Cliques in Sublinear Time, Sublinear-time algorithms for counting star subgraphs via edge sampling, Constructing near spanning trees with few local inspections, Almost stable matchings by truncating the Gale-Shapley algorithm, Round Compression for Parallel Matching Algorithms, Distributed discovery of large near-cliques, Local computation algorithms for graphs of non-constant degrees, Minimum Entropy Combinatorial Optimization Problems, Minimum entropy combinatorial optimization problems, No sublogarithmic-time approximation scheme for bipartite vertex cover, The Program of the Mini-Workshop, Sublinear Graph Approximation Algorithms, On Constant Time Approximation of Parameters of Bounded Degree Graphs, Dynamic Approximate Vertex Cover and Maximum Matching, Fast distributed algorithms for testing graph properties, Best of two local models: centralized local and distributed local algorithms, Local algorithms for sparse spanning graphs, Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection, An Efficient Partitioning Oracle for Bounded-Treewidth Graphs, A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling, A sublinear-time approximation scheme for bin packing, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time, Unnamed Item, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the hardness of approximating minimum vertex cover
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Property testing and its connection to learning and approximation
- Data Streams: Algorithms and Applications
- On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
- Estimating the weight of metric minimum spanning trees in sublinear-time
- The price of being near-sighted
- Distance Approximation in Bounded-Degree and General Sparse Graphs
- Approximating Average Parameters of Graphs
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Tight Bounds for Testing Bipartiteness in General Graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Automata, Languages and Programming
- Property testing in bounded degree graphs
