Approximating dynamic weighted vertex cover with soft capacities
From MaRDI portal
Publication:2072101
DOI10.1007/S00453-021-00886-9OpenAlexW3211379435MaRDI QIDQ2072101
Wing-Kai Hon, Chung-Shou Liao, Hao-Ting Wei, Kunihiko Sadakane, Paul S. Horn
Publication date: 1 February 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-021-00886-9
Cites Work
- Heuristics for the dynamic facility location problem with modular capacities
- Dynamic traveling salesman problem with stochastic release dates
- Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
- Maintaining a large matching and a small vertex cover
- Speeding Up Dynamic Shortest-Path Algorithms
- Covering Problems with Hard Capacities
- Design of Dynamic Algorithms via Primal-Dual Method
- Dynamic ordered sets with exponential search trees
- Worst-case update times for fully-dynamic all-pairs shortest paths
- 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
- Faster worst case deterministic dynamic connectivity
- 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
This page was built for publication: Approximating dynamic weighted vertex cover with soft capacities
