Dynamic matching with better-than-2 approximation in polylogarithmic update time
From MaRDI portal
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
Cites work
- A \((2+\epsilon)\)-approximation for maximum weight matching in the semi-streaming model
- A deamortization approach for dynamic spanner and dynamic maximal matching
- A framework for dynamic matching in weighted graphs
- A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- A simple augmentation method for matchings with applications to streaming algorithms
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Balls and bins: A study in negative dependence
- Better bounds for matchings in the streaming model
- Bipartite Graph Matchings in the Semi-streaming Model
- Deterministic (1+ 𝜀 )-approximate maximum matching with poly(1/ 𝜀 ) passes in the semi-streaming model and beyond
- Deterministic dynamic matching in \(O(1)\) update time
- Deterministic fully dynamic data structures for vertex cover and matching
- Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
- Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
- Dynamic (1+ )-approximate matching size in truly sublinear update time
- Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds
- Dynamic algorithms for maximum matching size
- Dynamic matching with better-than-2 approximation in polylogarithmic update time
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- Dynamic matrix inverse: improved algorithms and matching conditional lower bounds
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
- Faster dynamic matchings and vertex connectivity
- Faster fully dynamic matchings with small approximation ratios
- Fully dynamic (1+ e)-approximate matchings
- Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
- Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
- Fully dynamic matching in bipartite graphs
- Fully dynamic matching: \((2 - \sqrt{2})\)-approximation in polylog update time
- Fully Dynamic Matching: Beating 2-Approximation in Δϵ Update Time
- Fully dynamic maximal independent set in expected poly-log update time
- Fully dynamic maximal independent set with polylogarithmic update time
- Fully dynamic maximal matching in O( n) update time
- Fully dynamic maximal matching in constant update time
- Graph sketching against adaptive adversaries applied to the minimum degree algorithm
- Higher lower bounds from the 3SUM conjecture
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- scientific article; zbMATH DE number 7768364 (Why is no real title available?)
- scientific article; zbMATH DE number 7829326 (Why is no real title available?)
- scientific article; zbMATH DE number 7829328 (Why is no real title available?)
- scientific article; zbMATH DE number 7829343 (Why is no real title available?)
- scientific article; zbMATH DE number 7788450 (Why is no real title available?)
- Improved bounds for online preemptive matching
- Improved constant-time approximation algorithms for maximum matchings and other optimization problems
- Improved streaming algorithms for weighted matching, via unweighted matching
- Linear programming in the semi-streaming model with application to the maximum matching problem
- Linear-time approximation for maximum weight matching
- Maintaining a large matching and a small vertex cover
- Maintaining an EDCS in general graphs: simpler, density-sensitive and with worst-case time bounds
- Maximum matching and a polyhedron with 0,1-vertices
- Maximum matching in semi-streaming with few passes
- Maximum matching in two, three, and a few more passes over graph streams
- Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model
- Maximum matchings in dynamic graph streams and the simultaneous communication model
- New deterministic approximation algorithms for fully dynamic matching
- New trade-offs for fully dynamic matching via hierarchical EDCS
- On an estimate of the chromatic class of a \(p\)-graph
- On graph problems in a semi-streaming model
- On regularity lemma and barriers in streaming and dynamic matching
- On the hardness of partially dynamic graph problems and connections to diameter
- Paths, Trees, and Flowers
- Perfect matchings in O(n n) time in regular bipartite graphs
- Popular conjectures as a barrier for dynamic planar graph algorithms
- Popular conjectures imply strong lower bounds for dynamic problems
- Rounding dynamic matchings against an adaptive adversary
- Semi-streaming bipartite matching in fewer passes and optimal space
- Simplified and space-optimal semi-streaming (2+)-approximate matching
- Sublinear algorithms for (1.5+)-approximate matching
- Sublinear time algorithms and complexity of approximate maximum matching
- Time-optimal sublinear algorithms for matching and vertex cover
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
This page was built for publication: Dynamic matching with better-than-2 approximation in polylogarithmic update time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6993545)
