A tight bound for shortest augmenting paths on trees

The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well und...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2022-01, Vol.901, p.45-61
Main Authors: Bosek, Bartłomiej, Leniowski, Dariusz, Sankowski, Piotr, Zych-Pawlewicz, Anna
Format: Article
Language:English
Subjects:
Algorithm
Incremental
Matching
Online
Tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree T=(W⊎B,E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et al. [6] that the total length of all shortest augmenting paths found is O(nlog⁡n). In this paper we prove a tight O(nlog⁡n) upper bound for the total length of shortest augmenting paths for trees improving over O(nlog2⁡n) bound [3].
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2021.11.025