Sublinear time algorithms and complexity of approximate maximum matching
From MaRDI portal
Publication:6499229
DOI10.1145/3564246.3585231MaRDI QIDQ6499229
Aviad Rubinstein, Soheil Behnezhad, Mohammad Roghani
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Local computation algorithms for graphs of non-constant degrees
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- 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
- Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
- An improved constant-time approximation algorithm for maximum~matchings
- 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
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Sublinear time algorithms and complexity of approximate maximum matching
