Inferring a graph from path frequency
Inferring a graph from path frequency
复制标题
DOI：
10.1016/j.dam.2012.02.002
复制
发表时间：
2012-07-01
影响因子：
1.1
通讯作者：
Sadakane, Kunihiko
中科院分区：
文献类型：
--
作者：
Akutsu, Tatsuya;Fukagawa, Daiji;Sadakane, Kunihiko
本文考虑了从顶点标记路径的出现次数推断图的问题，这与图的原像问题密切相关：从其特征空间表示重建图。它表明，精确和近似版本的问题可以解决在多项式时间内的输出图的大小，通过使用动态规划算法，如果图是树的最大程度是由一个常数和给定的路径和字母大小的长度由常数所限定。另一方面，它表明，这个问题是强NP-困难的，即使是有界度的树，如果路径的最大长度没有界。还研究了从固定大小子串的出现次数推断串的问题。(C)2012 Elsevier B. V.保留所有权利。
This paper considers the problem of inferring a graph from the number of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs: to reconstruct a graph from its feature space representation. It is shown that both exact and approximate versions of the problem can be solved in polynomial time in the size of an output graph by using dynamic programming algorithms if the graphs are trees whose maximum degree is bounded by a constant and the lengths of given paths and alphabet size are bounded by constants. On the other hand, it is shown that this problem is strongly NP-hard even for trees of bounded degree if the maximum length of paths is not bounded. The problem of inferring a string from the number of occurrences of fixed size substrings is also studied. (C) 2012 Elsevier B.V. All rights reserved.