Sublinear time algorithms and complexity of approximate maximum matching
From MaRDI portal
Publication:6499229
DOI10.1145/3564246.3585231MaRDI QIDQ6499229FDOQ6499229
Authors: Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein 
Publication date: 8 May 2024
Cites Work
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Title not available (Why is that?)
- An improved constant-time approximation algorithm for maximum~matchings
- A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Local computation algorithms for graphs of non-constant degrees
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Fully dynamic matching in bipartite graphs
- Faster fully dynamic matchings with small approximation ratios
- Deterministically maintaining a \((2 + \epsilon)\)-approximate minimum vertex cover in \(O(1/\epsilon^2)\) amortized update time
- Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
- Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
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)
