The level ancestor problem simplified

DOI10.1007/3-540-45995-2_44MaRDI QIDQ3044351zbMATH OpenFDO

Authors Martin Farach-Colton, Michael A. Bender

Publication date 11 August 2004

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2286/22860508.htm

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Recommendations

• The level ancestor problem simplified
• Finding level-ancestors in trees
• The Level-Ancestor problem on pure pointer machines
• Finding level-ancestors in dynamic trees
• A fast cost-optimal parallel algorithm for the lowest common ancestor problem

Cited in

(16)

• Center location problems on tree graphs with subtree-shaped customers
• The Level-Ancestor problem on pure pointer machines
• Finding level-ancestors in trees
• String covers of a tree
• Morphing tree drawings in a small 3D grid
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Minimax regret path location on trees
• Finding level-ancestors in dynamic trees
• Succinct representations of permutations and functions
• Finding best swap edges minimizing the routing cost of a spanning tree
• The level ancestor problem simplified
• Computing the Longest Unbordered Substring
• Tight bounds for the number of absent subsequences
• Range minimization problems in path-facility location on trees
• Graph spanners for group Steiner distances

This page was built for publication: The level ancestor problem simplified

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