Finding level-ancestors in dynamic trees

DOI10.1007/BFB0028247MaRDI QIDQ4037405zbMATH OpenFDO

Authors Paul F. Dietz

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0028247

zbMATH Keywords

ancestor queries on tree

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improved algorithms for finding level ancestors in dynamic trees
• Finding level-ancestors in trees
• scientific article; zbMATH DE number 4047158
• The Level-Ancestor problem on pure pointer machines
• scientific article; zbMATH DE number 2086252

Cited in

(21)

• Center location problems on tree graphs with subtree-shaped customers
• The Level-Ancestor problem on pure pointer machines
• Finding level-ancestors in trees
• Finding lowest common ancestors in arbitrarily directed trees
• The k-neighbor, r-domination problems on interval graphs
• Top tree compression of tries
• Computing longest (common) Lyndon subsequences
• scientific article; zbMATH DE number 1670815 (Why is no real title available?)
• Dynamic weighted ancestors
• Longest common extensions in trees
• Longest common extensions in trees
• scientific article; zbMATH DE number 2086252 (Why is no real title available?)
• scientific article; zbMATH DE number 4047158 (Why is no real title available?)
• Succinct representations of permutations and functions
• Parent queries over dynamic balanced parenthesis strings
• The level ancestor problem simplified
• Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees
• Time efficient implementation for online k-server problem on trees
• Efficient algorithms for shortest distance queries on special classes of polygons
• Compressed dictionary matching on run-length encoded strings
• Compressed dictionary matching on run-length encoded strings

This page was built for publication: Finding level-ancestors in dynamic trees

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