Sublinear time algorithms and complexity of approximate maximum matching
From MaRDI portal
Cites work
- A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
- Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
- Faster fully dynamic matchings with small approximation ratios
- Fully dynamic matching in bipartite graphs
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- Local computation algorithms for graphs of non-constant degrees
- Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Cited in
(5)- Sublinear algorithms for TSP via path covers
- Dynamic matching with better-than-2 approximation in polylogarithmic update time
- Range counting oracles for geometric problems
- A 0.51-approximation of maximum matching in sublinear \(n^{1.5}\) time
- Minimizing makespan in sublinear time via weighted random sampling
This page was built for publication: Sublinear time algorithms and complexity of approximate maximum matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499229)
