Inferring a tree from walks
作者： Osamu Maruyama , Satoru Miyano
DOI: 10.1016/0304-3975(95)00156-5
关键词:
摘要: Abstract A walk on an undirected edge-colored graph G is a path containing all edges of . The tree inference from is, given string x colors, finding the smallest that realizes whose sequence edge-colors coincides with We prove problem solvable in O ( n ) time, where length string. furthermore consider inferring finite number partial walks, show turns to be NP-complete even if colors restricted 3. It also shown linear chain walks NP-complete, while single known polynomial time.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(14)
Osamu Maruyama, Satoru Miyano, Graph Inference from a Walk for TRees of Bounded Degree 3 is NP-Complete mathematical foundations of computer science. pp. 257- 266 ,(1995) , 10.1007/3-540-60246-1_132
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
E Mark Gold, Complexity of automaton identification from given data Information & Computation. ,vol. 37, pp. 302- 320 ,(1978) , 10.1016/S0019-9958(78)90562-4
Dana Angluin, On the complexity of minimum inference of regular sets Information & Computation. ,vol. 39, pp. 337- 350 ,(1978) , 10.1016/S0019-9958(78)90683-6
John Gallant, David Maier, James Astorer, On finding minimal length superstrings Journal of Computer and System Sciences. ,vol. 20, pp. 50- 58 ,(1980) , 10.1016/0022-0000(80)90004-5
Christos H. Papadimitriou, Mihalis Yannakakis, Optimization, approximation, and complexity classes Journal of Computer and System Sciences. ,vol. 43, pp. 425- 440 ,(1991) , 10.1016/0022-0000(91)90023-X
Vijay Raghavan, Bounded degree graph inference from walks Journal of Computer and System Sciences. ,vol. 49, pp. 108- 132 ,(1994) , 10.1016/S0022-0000(05)80089-3
Tao Jiang, Ming Li, Ding-zhu Du, A note on shortest superstrings with flipping Information Processing Letters. ,vol. 44, pp. 195- 199 ,(1992) , 10.1016/0020-0190(92)90084-9
Leonard Pitt, Manfred K. Warmuth, The minimum consistent DFA problem cannot be approximated within any polynomial Journal of the ACM (JACM). ,vol. 40, pp. 95- 142 ,(1993) , 10.1145/138027.138042
Ronald L. Rivest, Javed A. Aslam, Inferring graphs from walks conference on learning theory. pp. 359- 370 ,(1990) , 10.5555/92571.92670