Shortest Augmenting Paths for Online Matchings on Trees

DOI10.1007/978-3-319-28684-6_6zbMath1385.68055arXiv1704.02093OpenAlexW2408410772MaRDI QIDQ2788991

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

Publication date: 26 February 2016

Published in: Theoretical Computer Science, Approximation and Online Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

treesonline algorithmbipartite matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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 (1)

Shortest Augmenting Paths for Online Matchings on Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Shortest Augmenting Paths for Online Matchings on Trees
• Fully Dynamic Matching in Bipartite Graphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Online perfect matching and mobile computing
• Maintaining Assignments Online: Matching, Scheduling, and Flows
• Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching

This page was built for publication: Shortest Augmenting Paths for Online Matchings on Trees