The Heaviest Induced Ancestors Problem: Better Data Structures and Applications
The Heaviest Induced Ancestors Problem: Better Data Structures and Applications
复制标题
最严重的诱发祖先问题：更好的数据结构和应用程序
DOI：
10.1007/s00453-022-00955-7
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
Thankachan, Sharma V.
中科院分区：
文献类型：
--
作者：
Abedin, Paniz;Hooshmand, Sahar;Ganguly, Arnab;Thankachan, Sharma V.
假设这两棵树有根，叶子的数量相等.叶子被标记了，叶子的标记是中叶子的排列。节点与权重相关联，使得节点u的权重（由W（u）表示）大于其父节点的权重。一个节点和一个节点是诱导的，当且仅当它们的子树至少有一个公共的叶子标签。最重的诱导祖先查询与输入节点和要求输出具有最高组合权重的诱导节点对，例如是和的祖先。这在几个文本处理应用程序中是一个有用的原语。Gagie等人（第25届加拿大计算几何会议论文集，CCCG 2013，滑铁卢，安大略，加拿大，2013）介绍了这个问题，并提出了具有以下时空权衡的三种数据结构：（i）空间和查询时间，（ii）空间和查询时间，以及（iii）O（n）空间和查询时间。这里是两棵树中节点的个数，是一个任意小的常数.我们提出了两个新的数据结构，具有更好的空间和时间的权衡：（i）空间和查询时间，（ii）O（n）空间和查询时间。此外，我们提出了这些结果的新应用。
Letandbe two rooted trees with an equal number of leaves. The leaves are labeled, and the labeling of the leaves inis a permutation of those in. Nodes are associated with weight, such that the weight of a nodeu, denoted byW(u), is more than the weight of its parent. A nodeand a nodeare induced, iff their subtrees have at least one common leaf label. Aheaviest induced ancestorquerywith input nodesandasks to output the pairof induced nodes with the highest combined weight, such thatis an ancestor ofandis an ancestor of. This is a useful primitive in several text processing applications. Gagie et al. (Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG 2013, Waterloo, Ontario, Canada, 2013) introduced this problem and proposed three data structures with the following space-time trade-offs: (i)space andquery time, (ii)space andquery time, and (iii)O(n) space andquery time. Herenis the number of nodes in both trees combined andis an arbitrarily small constant. We present two new data structures with better space-time trade-offs: (i)space andquery time, and (ii)O(n) space andquery time. Additionally, we present new applications of these results.
登录
查看更多内容
查找所有κ-失配最大公共子串对的并行算法
DOI：
--
发表时间：
2016
期刊：
International Conference for High Performance Computing, Networking, Storage and Analysis
影响因子：
--
作者：
Sriram P. Chockalingam;Sharma V. Thankachan;S. Aluru
通讯作者：
S. Aluru
重温最重的诱发祖先问题
DOI：
10.4230/lipics.cpm.2018.20
发表时间：
2018
期刊：
{CPM} 2018
影响因子：
--
作者：
Abedin, P.;Hooshmand, S.;Ganguly, A.;Thankachan, S.V.
通讯作者：
Thankachan, S.V.
块编辑后更快地查询最长子串回文
DOI：
10.4230/lipics.cpm.2019.27
发表时间：
2019
期刊：
Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, LIPIcs
影响因子：
--
作者：
Mitsuru Funakoshi;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
通讯作者：
Masayuki Takeda
最长公共子串完全动态化
DOI：
--
发表时间：
2018
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
A. Amir;P. Charalampopoulos;S. Pissis;J. Radoszewski
通讯作者：
J. Radoszewski
编辑后的最长子串回文
DOI：
10.4230/lipics.cpm.2018.12
发表时间：
2018
期刊：
Proceedings of Annual Symposium on Combinatorial Pattern Matching 2018, LIPIcs
影响因子：
--
作者：
Mitsuru Funakoshi;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
通讯作者：
Masayuki Takeda