2026-07-22T16:59:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6067 2024-03-06T10:37:36Z ddc:004 open_access

The Nearest Colored Node in a Tree Gawrychowski, Pawel Landau, Gad M. Mozes, Shay Weimann, Oren Marked ancestor Vertex-label distance oracles Nearest colored descend- ant Top-trees 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 well-known 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 (link-cut operations). There is a known (top-tree 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pawel Gawrychowski and Gad M. Landau and Shay Mozes and Oren Weimann 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.25 urn:nbn:de:0030-drops-60674 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.25 eng https://creativecommons.org/licenses/by/3.0/legalcode