Abstract
We start a systematic study of data structures for the nearest colored node problem on trees. Given a tree with colored nodes and weighted edges, we want to answer queries (v,c) asking for the nearest node to node v that has color c. This is a natural generalization of the wellknown nearest marked ancestor problem. We give an O(n)space O(log log n)query solution and show that this is optimal. We also consider the dynamic case where updates can change a node's color and show that in O(n) space we can support both updates and queries in O(log n) time. We complement this by showing that O(polylog n) update time implies Omega(log n \ log log n) query time. Finally, we consider the case where updates can change the edges of the tree (linkcut operations). There is a known (toptree based) solution that requires update time that is roughly linear in the number of colors. We show that this solution is probably optimal by showing that a strictly sublinear update time implies a strictly subcubic time algorithm for the classical all pairs shortest paths problem on a general graph. We also consider versions where the tree is rooted, and the query asks for the nearest ancestor/descendant of node v that has color c, and present efficient data structures for both variants in the static and the dynamic setting.
BibTeX  Entry
@InProceedings{gawrychowski_et_al:LIPIcs:2016:6067,
author = {Pawel Gawrychowski and Gad M. Landau and Shay Mozes and Oren Weimann},
title = {{The Nearest Colored Node in a Tree}},
booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
pages = {25:125:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770125},
ISSN = {18688969},
year = {2016},
volume = {54},
editor = {Roberto Grossi and Moshe Lewenstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6067},
URN = {urn:nbn:de:0030drops60674},
doi = {10.4230/LIPIcs.CPM.2016.25},
annote = {Keywords: Marked ancestor, Vertexlabel distance oracles, Nearest colored descend ant, Toptrees}
}
Keywords: 

Marked ancestor, Vertexlabel distance oracles, Nearest colored descend ant, Toptrees 
Collection: 

27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) 
Issue Date: 

2016 
Date of publication: 

27.06.2016 