Deterministic fully dynamic data structures for vertex cover and matching
From MaRDI portal
Recommendations
- Deterministic fully dynamic data structures for vertex cover and matching
- Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
- Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
- Dynamic approximate vertex cover and maximum matching
- Deterministic dynamic matching in \(O(1)\) update time
Cited in
(32)- Dynamic algorithms via the primal-dual method
- Approximating dynamic weighted vertex cover with soft capacities
- Dynamic kernels for hitting sets and set packing
- Dynamic clustering to minimize the sum of radii
- Deterministic dynamic matching in \(O(1)\) update time
- Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
- Dynamic rank-maximal and popular matchings
- Fully dynamic matching in bipartite graphs
- Design of dynamic algorithms via primal-dual method
- Maintaining Near-Popular Matchings
- Deterministic fully dynamic data structures for vertex cover and matching
- Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
- scientific article; zbMATH DE number 6866348 (Why is no real title available?)
- Dynamic approximate vertex cover and maximum matching
- Local algorithms for bounded degree sparsifiers in sparse graphs
- Density independent algorithms for sparsifying k-step random walks
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
- An \(o(1)\)-approximation algorithm for dynamic weighted vertex cover with soft capacity
- Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
- Optimal lower bounds for matching and vertex cover in dynamic graph streams
- Improved algorithm for dynamic b-matching
- Dynamic clustering to minimize the sum of radii
- Round compression for parallel matching algorithms
- Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
- Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.
- Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
- Fully dynamic maintenance of vertex cover
- Simple dynamic spanners with near-optimal recourse against an adaptive adversary
- Deterministic rounding of dynamic fractional matchings
- Dynamic algorithms for submodular matching
- Minimizing recourse in an adaptive balls and bins game
This page was built for publication: Deterministic fully dynamic data structures for vertex cover and matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5362993)
