No sublogarithmic-time approximation scheme for bipartite vertex cover
Publication:2256970
DOI10.1007/S00446-013-0194-ZzbMath1320.68224OpenAlexW3104625252MaRDI QIDQ2256970
Publication date: 23 February 2015
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10138/37521
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Low diameter graph decompositions
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Survey of local algorithms
- Lower bounds for local approximation
- Local Computation
- Expander graphs and their applications
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- The price of being near-sighted
- A Local 2-Approximation Algorithm for the Vertex Cover Problem
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Large deviations for sums of partly dependent random variables
- What Can be Computed Locally?
- No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover
- Local Graph Partitions for Approximation and Testing
- What cannot be computed locally!
This page was built for publication: No sublogarithmic-time approximation scheme for bipartite vertex cover
