Improved algorithm for dynamic b-Matching

DOI10.4230/LIPICS.ESA.2017.15zbMATH Open1442.68161OpenAlexW2738466993MaRDI QIDQ5111701FDOQ5111701

Manoj Gupta, Divyarthi Mohan, Sayan Bhattacharya

Publication date: 27 May 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7844/pdf/LIPIcs-ESA-2017-15.pdf/

zbMATH Keywords

graph algorithmsdynamic data structures

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Online and dynamic algorithms for set cover
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Maintaining a large matching and a small vertex cover
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• Fully Dynamic Maximal Matching in O (log n) Update Time
• Fully Dynamic Matching in Bipartite Graphs
• Faster Fully Dynamic Matchings with Small Approximation Ratios
• Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
• Design of Dynamic Algorithms via Primal-Dual Method
• New deterministic approximation algorithms for fully dynamic matching

Cited In (2)

• Dynamic Matching Algorithms in Practice
• Lazy or eager dynamic matching may not be fast

This page was built for publication: Improved algorithm for dynamic b-Matching

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