Deterministic dynamic matching in worst-case update time
From MaRDI portal
Publication:6066769
DOI10.1007/s00453-023-01151-xarXiv2108.10461OpenAlexW3200817746MaRDI QIDQ6066769
Publication date: 13 December 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2108.10461
Cites Work
- On negatively associated random variables
- Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
- Maintaining a large matching and a small vertex cover
- Towards polynomial lower bounds for dynamic problems
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time
- Randomness conductors and constant-degree lossless expanders
- Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
- Faster Fully Dynamic Matchings with Small Approximation Ratios
- Higher Lower Bounds from the 3SUM Conjecture
- Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
- Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time
- Balls and bins: A study in negative dependence
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Online and dynamic algorithms for set cover
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
- Rounding dynamic matchings against an adaptive adversary
- Stochastic matching with few queries: (1-ε) approximation
- Fully Dynamic Matching: Beating 2-Approximation in Δϵ Update Time
- Dynamic set cover: improved algorithms and lower bounds
- Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
- (1 + ∊)-Approximate Incremental Matching in Constant Deterministic Amortized Time
- A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
- Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
- New deterministic approximation algorithms for fully dynamic matching
- The cell probe complexity of dynamic range counting
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Dynamic graph connectivity in polylogarithmic worst case time
- A framework for dynamic matching in weighted graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Deterministic dynamic matching in worst-case update time
