Loading...
Please wait, while we are loading the content...
Similar Documents
Kyushu University Institutional Repository Inferring a Tree from Walks
| Content Provider | Semantic Scholar |
|---|---|
| Author | Maruyama, Osamu |
| Abstract | 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 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 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://catalog.lib.kyushu-u.ac.jp/opac_download_md/3156/rifis-tr-51.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
