Document Open Access Logo

The Nearest Colored Node in a Tree

Authors Pawel Gawrychowski, Gad M. Landau, Shay Mozes, Oren Weimann

PDF
Thumbnail PDF

File

LIPIcs.CPM.2016.25.pdf
  • Filesize: 463 kB
  • 12 pages

Document Identifiers

Author Details

Pawel Gawrychowski
Gad M. Landau
Shay Mozes
Oren Weimann

Cite As Get BibTex

Pawel Gawrychowski, Gad M. Landau, Shay Mozes, and Oren Weimann. The Nearest Colored Node in a Tree. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CPM.2016.25

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 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.

Subject Classification

Keywords
  • Marked ancestor
  • Vertex-label distance oracles
  • Nearest colored descend- ant
  • Top-trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. I. Abraham, S. Chechik, R. Krauthgamer, and U. Wieder. Approximate nearest neighbor search in metrics of planar graphs. In 18th APPROX/RANDOM, pages 20-42, 2015. Google Scholar
  2. S. Alstrup, J. Holm, K. de Lichtenberg, and M. Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms (TALG), 1(2):243-264, 2005. Google Scholar
  3. S. Alstrup, T. Husfeldt, and T. Rauhe. Marked ancestor problems. Technical Report DIKU 98-8, Dept. Comput. Sc., Univ. Copenhagen, 1998. (Some of the results needed from here are not included in the FOCS’98 extended abstract). Google Scholar
  4. B. Belazzougui and G. Navarro. Optimal lower and upper bounds for representing sequences. ACM Transactions on Algorithms (TALG), 11(4):1-21, 2010. Google Scholar
  5. M.A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, and P. Sumazin. Lowest common ancestors in trees and directed acyclic graphs. Journal of Algorithms, 57(2):75-94, 2005. Google Scholar
  6. O. Berkman and U. Vishkin. Recursive star-tree parallel data structure. SIAM Journal on Computing, 22(2):221-242, 1993. Google Scholar
  7. P. Bille, G.M. Landau, R. Raman, S. Rao, K. Sadakane, and O. Weimann. Random access to grammar-compressed strings and trees. SIAM Journal on Computing (SICOMP), 44(3):513-539, 2015. Google Scholar
  8. S. Chechik. Improved distance oracles and spanners for vertex-labeled graphs. In 20th ESA, pages 325-336, 2012. Google Scholar
  9. M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R.E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738-761, 1994. Google Scholar
  10. M.L. Fredman, J. Komlós, and E. Szemerédi. Storing a sparse table with o(1) worst case access time. J. ACM, 31(3):538-544, 1984. Google Scholar
  11. D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-355, 1984. Google Scholar
  12. D. Hermelin, A. Levy, O. Weimann, and R. Yuster. Distance oracles for vertex-labeled graphs. In 38th ICALP, pages 490-501, 2011. Google Scholar
  13. M. Li, C. C. Ma, and L. Ning. (1 + ε)-distance oracles for vertex-labeled planar graphs. In 10th TAMC, pages 42-51, 2013. Google Scholar
  14. S. Mozes and E.E. Skop. Efficient vertex-label distance oracles for planar graphs. In 13th WAOA, pages 97-109, 2015. Google Scholar
  15. M. Pǎtraşcu and M. Thorup. Time-space trade-offs for predecessor search. In 38th STOC, pages 232-240, 2006. Google Scholar
  16. P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99-127, 1977. Announced by van Emde Boas at FOCS 1975. Google Scholar
  17. B.T. Wilkinson. Amortized bounds for dynamic orthogonal range reporting. In 22nd ESA, pages 842-856, 2014. Google Scholar
  18. D.E. Willard. Log-logarithmic worst-case range queries are possible in space θ(n). Inf. Process. Lett., 17(2):81-84, 1983. Google Scholar
  19. V. Vassilevska Williams and R. Williams. Subcubic equivalences between path, matrix and triangle problems. In 51st FOCS, pages 645-654, 2010. Google Scholar
  20. J. Łącki, J. Oćwieja, M. Pilipczuk, P. Sankowski, and A. Zych. The power of dynamic distance oracles: Efficient dynamic algorithms for the steiner tree. In 47th STOC, pages 11-20, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact