Dynamic Matching Algorithms in Practice

DOI10.4230/LIPICS.ESA.2020.58MaRDI QIDQ5874529zbMATH OpenOpenAlexFDO

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(^3 n) worst case update time
• Fully dynamic maximal matching in O( 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 + )-approximate incremental matching in constant deterministic amortized time

Cited in

(4)

• scientific article; zbMATH DE number 6863589 (Why is no real title available?)
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• Building and combining matching algorithms
• Lazy or eager dynamic matching may not be fast

Describes a project that uses

Uses Software

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

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)