2026-08-10T13:52:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8689 2024-03-06T10:43:02Z ddc:004 open_access

The Heaviest Induced Ancestors Problem Revisited Abedin, Paniz Hooshmand, Sahar Ganguly, Arnab Thankachan, Sharma V. Data Structure String Algorithms Orthogonal Range Queries We revisit the heaviest induced ancestors problem, which has several interesting applications in string matching. Let T_1 and T_2 be two weighted trees, where the weight W(u) of a node u in either of the two trees is more than the weight of u's parent. Additionally, the leaves in both trees are labeled and the labeling of the leaves in T_2 is a permutation of those in T_1. A node x in T_1 and a node y in T_2 are induced, iff their subtree have at least one common leaf label. A heaviest induced ancestor query HIA(u_1,u_2) is: given a node u_1 in T_1 and a node u_2 in T_2, output the pair (u_1^*,u_2^*) of induced nodes with the highest combined weight W(u^*_1) + W(u^*_2), such that u_1^* is an ancestor of u_1 and u^*_2 is an ancestor of u_2. Let n be the number of nodes in both trees combined and epsilon >0 be an arbitrarily small constant. Gagie et al. [CCCG' 13] introduced this problem and proposed three solutions with the following space-time trade-offs: - an O(n log^2n)-word data structure with O(log n log log n) query time - an O(n log n)-word data structure with O(log^2 n) query time - an O(n)-word data structure with O(log^{3+epsilon}n) query time. In this paper, we revisit this problem and present new data structures, with improved bounds. Our results are as follows. - an O(n log n)-word data structure with O(log n log log n) query time - an O(n)-word data structure with O(log^2 n/log log n) query time. As a corollary, we also improve the LZ compressed index of Gagie et al. [CCCG' 13] for answering longest common substring (LCS) queries. Additionally, we show that the LCS after one edit problem of size n [Amir et al., SPIRE' 17] can also be reduced to the heaviest induced ancestors problem over two trees of n nodes in total. This yields a straightforward improvement over its current solution of O(n log^3 n) space and O(log^3 n) query time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paniz Abedin and Sahar Hooshmand and Arnab Ganguly and Sharma V. Thankachan 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.20 urn:nbn:de:0030-drops-86898 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.20 eng https://creativecommons.org/licenses/by/3.0/legalcode