Shortest augmenting paths for online matchings on trees

DOI10.1007/s00224-017-9838-xzbMath1390.68768OpenAlexW2787900023MaRDI QIDQ1743118

Anna Zych-Pawlewicz, Piotr Sankowski, Bartłomiej Bosek, Dariusz Leniowski

Publication date: 12 April 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9838-x

zbMATH Keywords

bipartite matchingsdynamic graph algorithmsshortest augmenting pathsapproximate matchingsonline matchings

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Deterministic dynamic matching in \(O(1)\) update time

Cites Work

• Unnamed Item
• Constructing a perfect matching is in random NC
• A data structure for dynamic trees
• Fully Dynamic Matching in Bipartite Graphs
• AdWords and generalized online matching
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Dynamic Approximate Vertex Cover and Maximum Matching
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Online perfect matching and mobile computing
• Maintaining Assignments Online: Matching, Scheduling, and Flows
• Fully Dynamic Maximal Matching in O (log n) Update Time

This page was built for publication: Shortest augmenting paths for online matchings on trees