scientific article; zbMATH DE number 7375960

DOI10.4230/LIPIcs.ICALP.2018.33zbMath1499.68261MaRDI QIDQ5002703

Shay Solomon, Moses Charikar

Publication date: 28 July 2021

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

zbMATH Keywords

worst-case boundsmaximum matchingdynamic graph algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) 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
• A balanced search tree O(1) worst-case update time
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Maintaining a large matching and a small vertex cover
• Fully Dynamic Matching in Bipartite Graphs
• Faster Fully Dynamic Matchings with Small Approximation Ratios
• Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
• Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log³ n) Worst Case Update Time
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• New deterministic approximation algorithms for fully dynamic matching
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• Fully Dynamic Maximal Matching in O (log n) Update Time
• Dynamic graph connectivity in polylogarithmic worst case time

This page was built for publication: