{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:59:38Z","timestamp":1725562778350},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540642305"},{"type":"electronic","value":"9783540697053"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0028567","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:33:39Z","timestamp":1132644819000},"page":"276-286","source":"Crossref","is-referenced-by-count":5,"title":["On the approximation of finding A(nother) Hamiltonian cycle in cubic Hamiltonian graphs"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, Proc. of 33rd FOGS, pages 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon, R. Yuster, U. Zwick, Color-coding: anew method for finding simple paths, cycles and other small subgraphs within large graphs, Proc. of 26th STOC, pages 326\u2013335, 1994.","DOI":"10.1145\/195058.195179"},{"issue":"2","key":"25_CR3","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R. P. Dilworth","year":"1950","unstructured":"R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math. (2) 51 (1950), 161\u2013166.","journal-title":"Ann. Math."},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M. F\u00fcrer","year":"1994","unstructured":"M. F\u00fcrer, B. Raghavachari, Approximating the Minimum-Degree Steiner Tree to within One of Optimal, Journal of Algorithms, 17, pages 409\u2013423, 1994.","journal-title":"Journal of Algorithms"},{"key":"25_CR5","unstructured":"G. Galbiati, A. Morzenti, F. Maffioli, On the Approximability of some Maximum Spanning Tree Problems, to appear in Theoretical Computer Science."},{"issue":"4","key":"25_CR6","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, R. E. Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput. 5:4, pages 704\u2013714, 1976.","journal-title":"SIAM J. Comput."},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"R. M. Karp, Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher editors, Complexity of Computer Computations, pages 85\u2013103, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"D. Karger, R. Motwani, G. Ramkumar, On Approximating the Longest Path in a Graph, Proc. of 3rd Workshop on Algorithms and Data Structures, LNCS 709, pages 421\u2013432, 1993.","DOI":"10.1007\/3-540-57155-8_267"},{"key":"25_CR9","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N. Megiddo","year":"1991","unstructured":"N. Megiddo, C. Papadimitriou, On total functions, existence theorems and computational complexity, Theoretical Computer Science, 81, pages 317\u2013324, 1991.","journal-title":"Theoretical Computer Science"},{"key":"25_CR10","first-page":"239","volume":"25","author":"B. Monien","year":"1984","unstructured":"B. Monien, How to find long paths efficiently, Annals of Discrete Mathematics, 25, pages 239\u2013254, 1984.","journal-title":"Annals of Discrete Mathematics"},{"key":"25_CR11","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C. Papadimitriou","year":"1994","unstructured":"C. Papadimitriou, On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence, Journal of Computer and System Science 48, pages 498\u2013532, 1994.","journal-title":"Journal of Computer and System Science"},{"volume-title":"Combinatorial Optimization: Algorithms and Complexity","year":"1982","author":"C. Papadimitriou","key":"25_CR12","unstructured":"C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1982."},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou, M. Yannakakis, Optimization, Approximation and Complexity Classes, Journal of Computer and System Science 43, pages 425\u2013440, 1991.","journal-title":"Journal of Computer and System Science"},{"issue":"1","key":"25_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. Papadimitriou","year":"1993","unstructured":"C. Papadimitriou, M. Yannakakis, The traveling salesman problem with distances one and two, Mathematics of Operations Research, vol. 18, No. 1, pages 1\u201311, 1993.","journal-title":"Mathematics of Operations Research"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/S0167-5060(08)70511-9","volume":"3","author":"A. Thomason","year":"1978","unstructured":"A. Thomason, Hamilton cycles and uniquely edge colourable graphs, Ann. Discrete Math. 3, pages 259\u2013268, 1978.","journal-title":"Ann. Discrete Math."},{"key":"25_CR16","unstructured":"M. Yannakakis, personal communication, 1996."}],"container-title":["Lecture Notes in Computer Science","STACS 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T00:03:30Z","timestamp":1552953810000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540642305","9783540697053"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0028567","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}