Graph Inference from a Walk for TRees of Bounded Degree 3 is NP-Complete
Graph Inference from a Walk for TRees of Bounded Degree 3 is NP-Complete
复制标题
有界度 3 树的遍历的图推理是 NP 完全的
DOI：
10.1007/3-540-60246-1_132
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
S. Miyano
中科院分区：
文献类型：
--
作者：
O. Maruyama;S. Miyano
对一类无向边色图的游动的图推断是，给定一串颜色，找出允许遍历其边色序列为ISX的G中的所有边的最小图GinC，称为游动图。我们证明了有界度树的游动推论对于任意⩾3是NP完全的，而对于没有任何度界约束的树问题已知在O(N)时间内是可解的，其中是串的长度。此外，对于一类特殊的有界度为3的树，称为(1，1)-毛虫的问题被证明是NP-完全的。这与线性链的问题已知是可解的Ino(Nlogn)时间的情况形成对比，因为(1，1)毛毛虫是通过将一根长度的毛发至多附着到线性链的每个节点上而获得的。我们还证明了这些问题的MAXSNP-硬度。
The graph inference from a walk for a classCof undirected edge-colored graphs is, given a stringxof colors, finding the smallest graphGinCthat allows a traverse of all edges inGwhose sequence of edge-colors isx, called a walk forx. We prove that the graph inference from a walk for trees of bounded degreekis NP-complete for anyk⩾ 3, while the problem for trees without any degree bound constraint is known to be solvable inO(n) time, wherenis the length of the string. Furthermore, the problem for a special class of trees of bounded degree 3, called (1,1)-caterpillars, is shown to be NP-complete. This contrast with the case that the problem for linear chains is known to be solvable inO(nlogn) time since a (1,1)-caterpillar is obtained by attaching at most one hair of length one to each node of a linear chain. We also show the MAXSNP-hardness of these problems.