Sublinear time algorithms and complexity of approximate maximum matching
From MaRDI portal
Publication:6499229
Cites work
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- 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 + \epsilon)\)-approximate minimum vertex cover in \(O(1/\epsilon^2)\) amortized update time
- Faster fully dynamic matchings with small approximation ratios
- Fully dynamic matching in bipartite graphs
- 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
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)
