A Tight Bound for Shortest Augmenting Paths on Trees
A Tight Bound for Shortest Augmenting Paths on Trees
复制标题
树上最短增广路径的紧界
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Anna Zych
中科院分区：
文献类型：
--
作者：
B. Bosek;Dariusz Leniowski;P. Sankowski;Anna Zych
最短增广路径技术是最大匹配和最大流算法中使用的基本思想之一。自1972年由埃德蒙兹（Edmonds）和卡普（Karp）提出以来，它已在许多不同的情境中得到广泛应用。令人惊讶的是，尽管应用广泛，但即使在最简单的情况——树上的在线二分匹配问题中，它也仍未被很好地理解。在这个问题中，一个二分树（\(T=(W\cup B, E)\)）在线性呈现，即每一轮有一个来自\(B\)的顶点及其关联边到达。乔杜里（Chaudhuri）等人[7]推测，找到的所有最短增广路径的总长度为\(O(n\log n)\)。在本文中，我们证明了对于树的最短增广路径总长度的一个紧的\(O(n\log n)\)上界，改进了\(O(n\log^2 n)\)的界[5]。
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=(Wuplus 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. [7] that the total length of all shortest augmenting paths found is (O(n log n)). In this paper we prove a tight (O(n log n)) upper bound for the total length of shortest augmenting paths for trees improving over (O(n log ^2 n)) bound [5].