2016/11/21 by Harold N. Gabow, Gabow, Harold N.
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1611.07055
A preliminary version of results in this paper appeared in Proc.1st Annual ACM-SIAM Symp. on Disc. Algorithms (SODA), 1990
arxiv created 2016/11/21 · openalex publication_date 2016/11/21 · arxiv updated 2016/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 paper shows that a sequence of m such nca and link operations on a forest of n nodes can be processed on-line 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 \citeG17 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).