The nearest colored node in a tree

DOI10.1016/j.tcs.2017.08.021zbMath1386.68038OpenAlexW2751792305WikidataQ60143007 ScholiaQ60143007MaRDI QIDQ1698706

Shay Mozes, Oren Weimann, Paweł Gawrychowski, Gad M. Landau

Publication date: 16 February 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6067/

zbMATH Keywords

marked ancestornearest colored descendanttop-treesvertex-label distance oracles

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Internal dictionary matching

Cites Work

• Unnamed Item
• Compressed subsequence matching and packed tree coloring
• Efficient vertex-label distance oracles for planar graphs
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Improved Distance Oracles and Spanners for Vertex-Labeled Graphs
• Amortized Bounds for Dynamic Orthogonal Range Reporting
• Time-space trade-offs for predecessor search
• The Power of Dynamic Distance Oracles
• Maintaining information in fully dynamic trees with top trees
• Distance Oracles for Vertex-Labeled Graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Recursive Star-Tree Parallel Data Structure
• Design and implementation of an efficient priority queue
• Dynamic Perfect Hashing: Upper and Lower Bounds
• (1 + ε)-Distance Oracles for Vertex-Labeled Planar Graphs
• Optimal Lower and Upper Bounds for Representing Sequences
• Random Access to Grammar-Compressed Strings and Trees
• Approximate Nearest Neighbor Search in Metrics of Planar Graphs
• Lowest common ancestors in trees and directed acyclic graphs