Publication:5009521
From MaRDI portal
DOI10.4230/LIPIcs.APPROX-RANDOM.2018.27MaRDI QIDQ5009521
Chung-Shou Liao, Hao-Ting Wei, Paul S. Horn, Wing-Kai Hon, Kunihiko Sadakane
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1802.05623
Cites Work
- Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
- Maintaining a large matching and a small vertex cover
- Design of Dynamic Algorithms via Primal-Dual Method
- Dynamic ordered sets with exponential search trees
- Capacitated vertex covering
- Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
- Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Online and dynamic algorithms for set cover
- Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
- Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
- A new approach to dynamic all pairs shortest paths
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity