A Data Structure for Nearest Common Ancestors with Linking
Harold N. Gabow · ACM Transactions on Algorithms · 2017
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 + n log 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].