{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:20:44Z","timestamp":1737436844935,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540412557"},{"type":"electronic","value":"9783540409960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40996-3_14","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:17:32Z","timestamp":1188350252000},"page":"156-167","source":"Crossref","is-referenced-by-count":2,"title":["An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree"],"prefix":"10.1007","author":[{"given":"Q. S.","family":"Wu","sequence":"first","affiliation":[]},{"given":"C. L.","family":"Lu","sequence":"additional","affiliation":[]},{"given":"R. C. T.","family":"Lee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,1,29]]},"reference":[{"issue":"3","key":"14_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0020-0190(90)90064-5","volume":"35","author":"S. R. Arikati","year":"1990","unstructured":"S. R. Arikati and C. Pandu Rangan. Linear algorithm for optimal path cover problem on interval graphs. Inf. Process. Lett., 35(3):149\u2013153, 1990.","journal-title":"Inf. Process. Lett."},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. In Proc. 37th Annual IEEE Symposium on Foundations of Computer Science, pages 2\u201311. IEEE Computer Society, 1996.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"14_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation. Springer-Verlag, Berlin Heidelberg, 1999."},{"issue":"1","key":"14_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. S. Baker","year":"1994","unstructured":"B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153\u2013180, 1994.","journal-title":"Journal of the ACM"},{"issue":"4","key":"14_CR5","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1145\/179812.179818","volume":"41","author":"A. Blum","year":"1994","unstructured":"A. Blum, M. Li, J. Tromp, and M. Yannakakis. Linear approximation of shortest superstrings. Journal of the ACM, 41(4):630\u2013647, 1994.","journal-title":"Journal of the ACM"},{"key":"14_CR6","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BFb0066442","volume-title":"On covering the points of a graph with point disjoint paths","author":"F. T. Boesch","year":"1974","unstructured":"F. T. Boesch, S. Chen, and J. A. M. McHugh. On covering the points of a graph with point disjoint paths. In Lecture Notes in Mathematics, volume 46, pages 201\u2013212. Springer, Berlin, 1974."},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0020-0190(79)90011-5","volume":"8","author":"M. A. Bonuccelli","year":"1979","unstructured":"M. A. Bonuccelli and D. P. Bovet. Minimum node disjoint path covering for circular-arc graphs. Inf. Process. Lett., 8:159\u2013161, 1979.","journal-title":"Inf. Process. Lett."},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","volume":"52","author":"G. Galbiati","year":"1994","unstructured":"G. Galbiati, F. Maffioli, and A. Morzenti. A short note on the approximability of the maximum leaves spanning tree problem. Inf. Process. Lett., 52:45\u201349, 1994.","journal-title":"Inf. Process. Lett."},{"key":"14_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979."},{"issue":"3","key":"14_CR10","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1145\/321892.321897","volume":"22","author":"S. E. Goodman","year":"1975","unstructured":"S. E. Goodman, S. T. Hedetniemi, and P. J. Slater. Advances on the Hamiltonian completion problem. Journal of the ACM, 22(3):352\u2013360, 1975.","journal-title":"Journal of the ACM"},{"issue":"4","key":"14_CR11","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O. H. Ibarra","year":"1975","unstructured":"O. H. Ibarra and C. E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4):463\u2013468, 1975.","journal-title":"Journal of the ACM"},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0020-0190(76)90080-6","volume":"5","author":"S. Kundu","year":"1976","unstructured":"S. Kundu. A linear algorithm for the Hamiltonian completion number of a tree. Inf. Process. Lett., 5:55\u201357, 1976.","journal-title":"Inf. Process. Lett."},{"key":"14_CR13","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"E. L. Lawler. Combinatorial Optimization: Networks and Matroids, chapter 6. Holt, Rinehart and Winston, New York, 1976."},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/0020-0190(75)90057-5","volume":"4","author":"J. Misra","year":"1975","unstructured":"J. Misra and R. E. Tarjan. Optimal chain partitions of trees. Inf. Process. Lett., 4:24\u201326, 1975.","journal-title":"Inf. Process. Lett."},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43:425\u2013440, 1991.","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18:1\u201311, 1993.","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"14_CR17","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. Sahni and T. Gonzalez. P-complete approximation problems. Journal of the ACM, 23(3):555\u2013565, 1976.","journal-title":"Journal of the ACM"},{"key":"14_CR18","unstructured":"Z. Skupien. Path partitions of vertices and Hamiltonicity of graphs. In Proc. 2nd Czechoslovakian Symp. on Graph Theory, pages 481\u2013491, Prague, 1974."},{"issue":"2","key":"14_CR19","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/0304-3975(93)90123-B","volume":"115","author":"R. Srikant","year":"1993","unstructured":"R. Srikant, R. Sundaram, K. S. Singh, and C. P. Rangan. Optimal path cover problem on block graphs and bipartite permutation graphs. Theoretical Computer Science, 115(2):351\u2013357, 1993.","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"14_CR20","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0304-3975(98)00180-7","volume":"225","author":"P.-K. Wong","year":"1999","unstructured":"P.-K. Wong. Optimal path cover problem on block graphs. Theoretical Computer Science, 225(1-2):163\u2013169, 1999.","journal-title":"Theoretical Computer Science"},{"key":"14_CR21","volume-title":"On the Complexity and Approximability of Some Hamiltonian Path Problems","author":"Q. S. Wu","year":"2000","unstructured":"Q. S. Wu. On the Complexity and Approximability of Some Hamiltonian Path Problems. PhD Thesis, National Tsing Hua University, Taiwan, 2000."},{"key":"14_CR22","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0020-0190(94)00158-8","volume":"52","author":"J. H. Yan","year":"1994","unstructured":"J. H. Yan and G. J. Chang. The path-partition problem in block graphs. Inf. Process. Lett., 52:317\u2013322, 1994.","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40996-3_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T18:25:52Z","timestamp":1737397552000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40996-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412557","9783540409960"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-40996-3_14","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}