A Data Structure for Nearest Common Ancestors with Linking
A Data Structure for Nearest Common Ancestors with Linking
复制标题
具有链接的最近共同祖先的数据结构
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
H. Gabow
中科院分区：
文献类型：
--
作者：
H. Gabow
考虑一个通过链接操作进化的森林，链接操作使一棵树的根节点成为另一棵树中节点的子节点。与链接操作混合的是nca操作，当存在时，它返回两个给定节点的最近共同祖先。这篇文章证明了在一个n个节点的森林上的m个这样的nca和link操作的序列可以在O（mα（m，n）+n）的时间内在线处理。这在以前仅对于受限类型的链接操作是已知的。在Edmonds的算法中，一个链接只通过添加一个新的叶子来扩展一棵树，这种特殊情况发生在一般图上寻找最大权重匹配的算法中。将我们的算法扩展到[9]中Edmonds算法的实现中，实现了加权匹配的时间O（n（m + nlog n）），这是一个可以证明的最佳渐近界（n和m分别是顶点和边的数量）。我们的数据结构还提供了Gabow和Tarjan [11]的增量树集合合并算法的简单替代实现。
Consider a forest that evolves via link operations that make the root of one tree the child of a node in another tree. Intermixed with link operations are nca operations, which return the nearest common ancestor of two given nodes when such exists. This article shows that a sequence of m such nca and link operations on a forest of n nodes can be processed online in time O(mα (m,n)+n). This was previously known only for a restricted type of link operation. The special case where a link only extends a tree by adding a new leaf occurs in Edmonds’ algorithm for finding a maximum weight matching on a general graph. Incorporating our algorithm into the implementation of Edmonds’ algorithm in [9] achieves time O(n(m + nlog n)) for weighted matching, an arguably optimum asymptotic bound (n and m are the number of vertices and edges, respectively). Our data structure also provides a simple alternative implementation of the incremental-tree set merging algorithm of Gabow and Tarjan [11].