{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,8]],"date-time":"2026-11-08T05:04:55Z","timestamp":1794114295018,"version":"4.8.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,5,1]],"date-time":"1997-05-01T00:00:00Z","timestamp":862444800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1997,5]]},"DOI":"10.1007\/bf02523689","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T00:02:35Z","timestamp":1162944155000},"page":"82-98","source":"Crossref","is-referenced-by-count":155,"title":["On approximating the longest path in a graph"],"prefix":"10.1007","volume":"18","author":[{"given":"D.","family":"Karger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Motwani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G. D. S.","family":"Ramkumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02523689_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems,Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"BF02523689_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra, Approximating clique is NP-complete,Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 2\u201313.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"BF02523689_CR3","unstructured":"M. Bellare, Interactive Proofs and Approximation, IBM Research Report RC 17969, 1992."},{"key":"BF02523689_CR4","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman and G. Schnitger, On the complexity of approximating the independent set problem,Information and Computation,96 (1992), 77\u201394.","journal-title":"Information and Computation"},{"key":"BF02523689_CR5","doi-asserted-by":"crossref","unstructured":"A. Blum, Some tools for approximate 3-coloring,Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 1990, pp. 554\u2013562.","DOI":"10.1109\/FSCS.1990.89576"},{"key":"BF02523689_CR6","volume-title":"Random Graphs","author":"B. Bollobas","year":"1985","unstructured":"B. Bollobas,Random Graphs, Academic Press, New York, 1985."},{"key":"BF02523689_CR7","series-title":"Proceedings of the 2nd Scandanavian Workshop on Algorithmic Theory","first-page":"13","volume-title":"Approximating maximum independent sets by excluding subgraphs","author":"R. B. Boppana","year":"1990","unstructured":"R. B. Boppana and M. M. Halldorsson, Approximating maximum independent sets by excluding subgraphs,Proceedings of the 2nd Scandanavian Workshop on Algorithmic Theory, Lecture Notes in Computer Science, No. 447, Springer-Verlag, Berlin, 1990, pp. 13\u201325."},{"key":"BF02523689_CR8","doi-asserted-by":"crossref","unstructured":"A. Broder, A. M. Frieze, and E. Shamir, Finding hidden Hamiltonian cycles,Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 182\u2013189.","DOI":"10.1145\/103418.103442"},{"key":"BF02523689_CR9","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","volume":"5","author":"V. Chvatal","year":"1973","unstructured":"V. Chvatal, Tough graphs and Hamiltonian circuits,Discrete Mathematics,5 (1973), 215\u2013228.","journal-title":"Discrete Mathematics"},{"key":"BF02523689_CR10","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01580109","volume":"5","author":"V. Chvatal","year":"1973","unstructured":"V. Chvatal, Edmonds polytopes and weakly Hamiltonian graphs,Mathematical Programming,5 (1973), 29\u201340.","journal-title":"Mathematical Programming"},{"key":"BF02523689_CR11","first-page":"402","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"V. Chvatal","year":"1985","unstructured":"V. Chvatal, Hamiltonian cycles, inThe Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (ed. E. L. Lawleret al.), Wiley, New York, 1985, pp. 402\u2013430."},{"key":"BF02523689_CR12","volume-title":"Complexity of Computer Computations","author":"R. Fagin","year":"1974","unstructured":"R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, inComplexity of Computer Computations (ed. R. Karp), American Mathematical Society, Providence, RI, 1974."},{"key":"BF02523689_CR13","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra, and M. Szegedy, Approximating clique is almost NP-complete,Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 2\u201312.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"BF02523689_CR14","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. F. Vega de la","year":"1981","unstructured":"W. F. de la Vega and G. S. Lueker, Bin packing can be solved within 1+\u03b5 in linear time,Combinatorica,1 (1981), 349\u2013355.","journal-title":"Combinatorica"},{"key":"BF02523689_CR15","unstructured":"M. Furer and B. Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree,Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 317\u2013324."},{"key":"BF02523689_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979."},{"key":"BF02523689_CR17","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1016\/0196-6774(92)90052-E","volume":"13","author":"D. S. Johnson","year":"1992","unstructured":"D. S. Johnson, The Tale of the Second Prover, The NP-Completeness Column: An Ongoing Guide,Journal of Algorithms,13 (1992), 502\u2013524.","journal-title":"Journal of Algorithms"},{"key":"BF02523689_CR18","doi-asserted-by":"crossref","unstructured":"D. R. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming,Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 2\u201313.","DOI":"10.1109\/SFCS.1994.365710"},{"key":"BF02523689_CR19","doi-asserted-by":"crossref","unstructured":"N. Karmakar and R. M. Karp, An efficient approximation scheme for the one-dimensional bin packing problem,Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, pp. 312\u2013320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"BF02523689_CR20","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis, On the hardness of approximating minimization problems,Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 286\u2013293.","DOI":"10.1145\/167088.167172"},{"key":"BF02523689_CR21","first-page":"239","volume":"25","author":"B. Monien","year":"1984","unstructured":"B. Monien, How to find long paths efficiently,Annals of Discrete Mathematics,25 (1984), 239\u2013254.","journal-title":"Annals of Discrete Mathematics"},{"key":"BF02523689_CR22","unstructured":"R. Motwani, Lecture Notes on Approximation Algorithms, Technical Report No. STAN-CS-92-1435, Department of Computer Science, Stanford University, 1992."},{"key":"BF02523689_CR23","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes,Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 229\u2013234.","DOI":"10.1145\/62212.62233"},{"key":"BF02523689_CR24","doi-asserted-by":"crossref","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 (1993), 1\u201311.","journal-title":"Mathematics of Operations Research"},{"key":"BF02523689_CR25","unstructured":"A. Subramanian, Personal communication, 1994."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523689.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523689\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:39:44Z","timestamp":1558283984000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523689"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,5]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,5]]}},"alternative-id":["BF02523689"],"URL":"https:\/\/doi.org\/10.1007\/bf02523689","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,5]]}}}