Dynamic Matching Algorithms in Practice

DOI10.4230/LIPICS.ESA.2020.58OpenAlexW3082437107MaRDI QIDQ5874529FDOQ5874529

Authors

Publication date 7 February 2023

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

zbMATH Keywords

matchingdynamic matchingblossom algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Optimal dynamic matching
• New deterministic approximation algorithms for fully dynamic matching
• scientific article; zbMATH DE number 6863589
• Improved algorithm for dynamic \(b\)-matching
• Deterministic dynamic matching in worst-case update time
• Dynamic and self-stabilizing distributed matching
• Dynamically stable matching
• On adaptive algorithms for maximum matching
• Dynamic directed random matching

Cites Work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• A simple approximation algorithm for the weighted matching problem
• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• Benchmarking optimization software with performance profiles.
• Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
• Deterministic fully dynamic data structures for vertex cover and matching
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Engineering Algorithms for Approximate Weighted Matching
• Faster dynamic matchings and vertex connectivity
• Faster fully dynamic matchings with small approximation ratios
• Faster fully dynamic transitive closure in practice
• Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
• Fully dynamic approximate maximum matching and minimum vertex cover in \(O(\log^3 n)\) worst case update time
• Fully dynamic maximal matching in \(O(\log n)\) update time
• Maintaining a large matching and a small vertex cover
• New deterministic approximation algorithms for fully dynamic matching
• Paths, Trees, and Flowers
• Shrinking Trees not Blossoms: A Recursive Maximum Matching Approach
• TWO THEOREMS IN GRAPH THEORY
• \((1 + \varepsilon)\)-approximate incremental matching in constant deterministic amortized time

Cited In (4)

• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)
• Building and combining matching algorithms
• Lazy or eager dynamic matching may not be fast

Uses Software

• LEDA
• Boost C++ Libraries
• SNAP
• SparseMatrix
• Boost
• KONECT
• BGL

This page was built for publication: Dynamic Matching Algorithms in Practice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874529)