Inferring a Tree from Walks
Inferring a Tree from Walks
复制标题
从步行中推断出一棵树
DOI：
10.1016/0304-3975(95)00156-5
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
S. Miyano
中科院分区：
文献类型：
--
作者：
O. Maruyama;S. Miyano
无向边色图G上的游程是包含G的所有边的一条路。游程的树推论是，给定一个颜色串x，找出实现边颜色序列与x重合的游程的最小树。我们证明了这个问题在O(N)时间内是可解的，其中n是给定串的长度。我们进一步考虑了从有限个部分行走推断树的问题，其中G上的部分行走是G中的一条路。我们证明了即使颜色数被限制为3，这个问题也变成了NP-完全的。我们还证明了从部分行走推断线性链的问题是NP-完全的，而由一条行走推断的线性链在多项式时间内是可解的。
A walk on an undirected edge-colored graph G is a path containing all edges of G. The tree inference from a walk is, given a string x of colors, finding the smallest tree that realizes a walk whose sequence of edge-colors coincides with x. We prove that the problem is solvable in O(n) time, where n is the length of a given string. We furthermore consider the problem of inferring a tree from a finite number of partial walks, where a partial walk on G is a path in G. We show that the problem turns to be NP-complete even if the number of colors is restricted to 3. It is also shown that the problem of inferring a linear chain from partial walks is NP-complete, while the linear chain inference from a single walk is known to be solvable in polynomial time.