{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T10:55:49Z","timestamp":1763808949433,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_74","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:15:37Z","timestamp":1279044937000},"page":"871-883","source":"Crossref","is-referenced-by-count":36,"title":["Efficient Algorithms for the Longest Path Problem"],"prefix":"10.1007","author":[{"given":"Ryuhei","family":"Uehara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yushi","family":"Uno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"74_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-Coding. J. ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"74_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Heidelberg (1999)"},{"unstructured":"Balister, P.N., Gy\u00f6ri, E., Lehel, J., Schelp, R.H.: Longest Paths in Circular Arc Graphs. Technical report, U. of Memphis (2002), \n                    http:\/\/www.msci.memphis.edu\/preprint.html","key":"74_CR3"},{"key":"74_CR4","volume-title":"Hypergraphs","author":"C. Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs. Elsevier, Amsterdam (1989)"},{"issue":"2","key":"74_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(83)90078-9","volume":"17","author":"A.A. Bertossi","year":"1983","unstructured":"Bertossi, A.A.: Finding Hamiltonian Circuits in Proper Interval Graphs. Info. Proc. Lett.\u00a017(2), 97\u2013101 (1983)","journal-title":"Info. Proc. Lett."},{"key":"74_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(86)90135-3","volume":"23","author":"A.A. Bertossi","year":"1986","unstructured":"Bertossi, A.A., Bonuccelli, M.A.: Hamiltonian Circuits in Interval Graph Generalizations. Info. Proc. Lett.\u00a023, 195\u2013200 (1986)","journal-title":"Info. Proc. Lett."},{"issue":"6","key":"74_CR7","doi-asserted-by":"publisher","first-page":"1395","DOI":"10.1137\/S0097539702416761","volume":"32","author":"A. Bj\u00f6rklund","year":"2003","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Finding a Path of Superlogarithmic Length. SIAM J. Comput.\u00a032(6), 1395\u20131402 (2003)","journal-title":"SIAM J. Comput."},{"key":"74_CR8","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms. J. Comput. Syst. Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"74_CR9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"74_CR10","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0020-0190(01)00198-3","volume":"81","author":"R.W. Bulterman","year":"2002","unstructured":"Bulterman, R.W., van der Sommen, F.W., Zwaan, G., Verhoeff, T., van Gasteren, A.J.M., Feijen, W.H.J.: On Computing a Longest Path in a Tree. Info. Proc. Lett.\u00a081, 93\u201396 (2002)","journal-title":"Info. Proc. Lett."},{"key":"74_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(89)90059-8","volume":"32","author":"P. Damaschke","year":"1989","unstructured":"Damaschke, P.: The Hamiltonian Circuit Problem for Circle Graphs is NP-complete. Info. Proc. Lett.\u00a032, 1\u20132 (1989)","journal-title":"Info. Proc. Lett."},{"key":"74_CR12","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0012-365X(93)90223-G","volume":"112","author":"P. Damaschke","year":"1993","unstructured":"Damaschke, P.: Paths in Interval Graphs and Circular Arc Graphs. Discr. Math.\u00a0112, 49\u201364 (1993)","journal-title":"Discr. Math."},{"key":"74_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"74_CR14","first-page":"434","volume-title":"Proc. 1st Ann. ACM-SIAM Symp. on Discr. Algo.","author":"H.N. Gabow","year":"1990","unstructured":"Gabow, H.N.: Data Structures for Weighted Matching and Nearest Common Ancestors with Linking. In: Proc. 1st Ann. ACM-SIAM Symp. on Discr. Algo., pp. 434\u2013443. ACM, New York (1990)"},{"key":"74_CR15","volume-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"74_CR16","volume-title":"2\/e. Ann. Discr. Math.","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. In: Ann. Discr. Math., vol.\u00a057, 2\/e. Elsevier, Amsterdam (2004)"},{"unstructured":"Hochbaum, D.: Approximation Algorithms for NP-hard Problems. PWS Publishing Company (1995)","key":"74_CR17"},{"key":"74_CR18","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D. Karger","year":"1997","unstructured":"Karger, D., Motwani, R., Ramkumar, G.D.S.: On Approximating the Longest Path in a Graph. Algorithmica\u00a018, 82\u201398 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"74_CR19","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"Korte, N., M\u00f6hring, R.H.: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs. SIAM J. Comput\u00a018(1), 68\u201381 (1989)","journal-title":"SIAM J. Comput"},{"key":"74_CR20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0012-365X(93)E0077-H","volume":"135","author":"N.V.R. Mahadev","year":"1994","unstructured":"Mahadev, N.V.R., Peled, U.N.: Longest Cycles in Threshold Graphs. Discr. Math.\u00a0135, 169\u2013176 (1994)","journal-title":"Discr. Math."},{"key":"74_CR21","first-page":"239","volume":"25","author":"B. Monien","year":"1985","unstructured":"Monien, B.: How to Find Long Paths Efficiently. Ann. Discr. Math.\u00a025, 239\u2013254 (1985)","journal-title":"Ann. Discr. Math."},{"key":"74_CR22","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H. M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: Hamiltonian Circuit in Chordal Bipartite Graphs. Disc. Math.\u00a0156, 291\u2013298 (1996)","journal-title":"Disc. Math."},{"issue":"3","key":"74_CR23","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1016\/S0377-2217(02)00433-2","volume":"148","author":"M.G. Scutell\u00e0","year":"2003","unstructured":"Scutell\u00e0, M.G.: An Approximation Algorithm for Computing Longest Paths. European J. Oper. Res.\u00a0148(3), 584\u2013590 (2003)","journal-title":"European J. Oper. Res."},{"key":"74_CR24","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J. Spinrad","year":"1987","unstructured":"Spinrad, J., Brandst\u00e4dt, A., Stewart, L.: Bipartite Permutation Graphs. Discr. Appl. Math.\u00a018, 279\u2013292 (1987)","journal-title":"Discr. Appl. Math."},{"key":"74_CR25","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"key":"74_CR26","first-page":"680","volume-title":"Proc. 11th Ann. ACM-SIAM Symp. on Discr. Algo.","author":"S. Vishwanathan","year":"2000","unstructured":"Vishwanathan, S.: An Approximation Algorithm for Finding a Long Path in Hamiltonian Graphs. In: Proc. 11th Ann. ACM-SIAM Symp. on Discr. Algo., pp. 680\u2013685. ACM, New York (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_74","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,11]],"date-time":"2023-02-11T01:17:37Z","timestamp":1676078257000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_74","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}