scientific article; zbMATH DE number 7375934

DOI10.4230/LIPIcs.ICALP.2018.7zbMath1499.68245arXiv1711.06625MaRDI QIDQ5002673

Sarel Cohen, Moab Arar, David Wajc, Shiri Chechik, Clifford Stein

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1711.06625

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

maximum matchingdynamic matchingmaximum-weight matchingworst-case update time

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

Deterministic dynamic matching in worst-case update time ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Dynamic Matching Algorithms in Practice ⋮ Deterministic dynamic matching in \(O(1)\) update time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple reduction from maximum weight matching to maximum cardinality matching
• Maximum weight bipartite matching in matrix multiplication time
• Fully dynamic all pairs shortest paths with real edge weights
• Maintaining Minimum Spanning Forests in Dynamic Graphs
• Maintaining a large matching and a small vertex cover
• Linear-Time Approximation for Maximum Weight Matching
• Fully Dynamic Matching in Bipartite Graphs
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Incremental algorithms for minimal length paths
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Faster Fully Dynamic Matchings with Small Approximation Ratios
• Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
• On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
• Higher Lower Bounds from the 3SUM Conjecture
• Fully dynamic all-pairs shortest paths with worst-case update-time revisited
• Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log³ n) Worst Case Update Time
• Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m^10/7 log W) Time (Extended Abstract)
• Faster Scaling Algorithms for Network Problems
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Fibonacci heaps and their uses in improved network optimization algorithms
• Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Algorithm Theory - SWAT 2004
• New deterministic approximation algorithms for fully dynamic matching
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths
• Multiplying matrices faster than coppersmith-winograd
• A new approach to dynamic all pairs shortest paths
• Fully Dynamic Maximal Matching in O (log n) Update Time
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

This page was built for publication: