Shortest Augmenting Paths for Online Matchings on Trees

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

Bartłomiej Bosek, Piotr Sankowski, Dariusz Leniowski, 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

trees; online algorithm; bipartite matching

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W27: Online algorithms; streaming algorithms