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

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
• scientific article; zbMATH DE number 7561564
• Dynamic directed random matching

zbMATH Keywords

matchingdynamic matchingblossom algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• Benchmarking optimization software with performance profiles.
• Paths, Trees, and Flowers
• Title not available (Why is that?)
• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• A simple approximation algorithm for the weighted matching problem
• TWO THEOREMS IN GRAPH THEORY
• Title not available (Why is that?)
• Title not available (Why is that?)
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Maintaining a large matching and a small vertex cover
• Faster Fully Dynamic Matchings with Small Approximation Ratios
• Engineering Algorithms for Approximate Weighted Matching
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
• Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log³ n) Worst Case Update Time
• Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
• New deterministic approximation algorithms for fully dynamic matching
• Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
• Title not available (Why is that?)
• Faster fully dynamic transitive closure in practice
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• Shrinking Trees not Blossoms: A Recursive Maximum Matching Approach
• (1 + ∊)-Approximate Incremental Matching in Constant Deterministic Amortized Time

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)