A Data Structure for Nearest Common Ancestors with Linking

DOI10.1145/3108240MaRDI QIDQ4554935zbMATH OpenOpenAlexFDO

Authors Harold N. Gabow

Publication date 12 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.07055

zbMATH Keywords

disjoint-set data structureleast common ancestorsmatching algorithmsset merging

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Abstract: 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(malpha(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 cite{G17} achieves time $O(n(m+nlogn))$ for weighted matching, an arguably optimum asymptotic bound ($n$ and $m$ are the number of vertices and edges, respectively).

Recommendations

• Fast Algorithms for Finding Nearest Common Ancestors
• Near-optimal labeling schemes for nearest common ancestors
• scientific article; zbMATH DE number 4047158
• The nearest common ancestor in a dynamic tree
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• Finding least common ancestors in directed acyclic graphs
• Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
• Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees
• The heaviest induced ancestors problem: better data structures and applications
• Finding lowest common ancestors in arbitrarily directed trees

Cited in

(5)

• The nearest common ancestor in a dynamic tree
• The heaviest induced ancestors problem: better data structures and applications
• Fast Algorithms for Finding Nearest Common Ancestors
• Blocking trails for \(f\)-factors of multigraphs
• Traversing combinatorial 0/1-polytopes via optimization

This page was built for publication: A Data Structure for Nearest Common Ancestors with Linking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554935)