| 作成者 |
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
A walk in 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 se...quence 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 in 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.続きを見る
|
Mendeley出力
rifis-tr-51