Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified Framework
cs.DS
Submitted: 2026-11-01
Updated: 2026-11-01
Terminology
Sources
- Decremental Matching in General Graphs
- Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model
- Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b--Matching Problems in Nonbipartite Graphs
- Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints
- Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space
- Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
- A Simple $(1-\epsilon)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
- From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
- Matching Composition and Efficient Weight Reduction in Dynamic Matching
- Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
- Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
- Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
- Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
- Entropy Regularization and Faster Decremental Matching in General Graphs
- Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
- Weighted Matchings via Unweighted Augmentations
- Fully Dynamic $(1+\epsilon)$-Approximate Matchings
- $(1-\epsilon)$-Approximate Maximum Weighted Matching in Distributed, Parallel, and Semi-Streaming Settings
- Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time