{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T08:08:19Z","timestamp":1778054899907,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,5,12]],"date-time":"2010-05-12T00:00:00Z","timestamp":1273622400000},"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":[[2011,10]]},"DOI":"10.1007\/s00453-010-9411-3","type":"journal-article","created":{"date-parts":[[2010,5,11]],"date-time":"2010-05-11T15:59:03Z","timestamp":1273593543000},"page":"320-341","source":"Crossref","is-referenced-by-count":29,"title":["The Longest Path Problem has a Polynomial Solution on Interval Graphs"],"prefix":"10.1007","volume":"61","author":[{"given":"Kyriaki","family":"Ioannidou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stavros D.","family":"Nikolopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,5,12]]},"reference":[{"key":"9411_CR1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0020-0190(90)90064-5","volume":"35","author":"S.R. Arikati","year":"1990","unstructured":"Arikati, S.R., Pandu\u00a0Rangan, C.: Linear algorithm for optimal path cover problem on interval graphs. Inf. Process. Lett. 35, 149\u2013153 (1990)","journal-title":"Inf. Process. Lett."},{"key":"9411_CR2","author":"K. Asdre","year":"2009","unstructured":"Asdre, K., Nikolopoulos, S.D.: The 1-fixed-endpoint path cover problem is polynomial on interval graphs. Algorithmica (2009). doi: 10.1007\/s00453-009-9292-5","journal-title":"Algorithmica"},{"key":"9411_CR3","doi-asserted-by":"crossref","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. Inf. Process. Lett. 17, 97\u2013101 (1983)","journal-title":"Inf. Process. Lett."},{"key":"9411_CR4","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0020-0190(01)00198-3","volume":"81","author":"R. Bulterman","year":"2002","unstructured":"Bulterman, R., van\u00a0der Sommen, F., Zwaan, G., Verhoeff, T., van Gasteren, A., Feijen, W.: On computing a longest path in a tree. Inf. Process. Lett. 81, 93\u201396 (2002)","journal-title":"Inf. Process. Lett."},{"key":"9411_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1097-0037(199908)34:1<1::AID-NET1>3.0.CO;2-C","volume":"34","author":"M.S. Chang","year":"1999","unstructured":"Chang, M.S., Peng, S.L., Liaw, J.L.: Deferred-query: an efficient approach for some problems on interval graphs. Networks 34, 1\u201310 (1999)","journal-title":"Networks"},{"key":"9411_CR6","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/BF00571188","volume":"8","author":"P. Damaschke","year":"1992","unstructured":"Damaschke, P., Deogun, J.S., Kratsch, D., Steiner, G.: Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm. Order 8, 383\u2013391 (1992)","journal-title":"Order"},{"key":"9411_CR7","doi-asserted-by":"crossref","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. Inf. Process. Lett. 32, 1\u20132 (1989)","journal-title":"Inf. Process. Lett."},{"key":"9411_CR8","doi-asserted-by":"crossref","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. Discrete Math. 112, 49\u201364 (1993)","journal-title":"Discrete Math."},{"key":"9411_CR9","first-page":"166","volume-title":"Proc. of the 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"T. Feder","year":"2005","unstructured":"Feder, T., Motwani, R.: Finding large cycles in Hamiltonian graphs. In: Proc. of the 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 166\u2013175. ACM, New York (2005)"},{"key":"9411_CR10","first-page":"407","volume-title":"Proc. of the 36th Annual ACM Symp. on Theory of Computing (STOC)","author":"H.N. Gabow","year":"2004","unstructured":"Gabow, H.N.: Finding paths and cycles of superpolylogarithmic length. In: Proc. of the 36th Annual ACM Symp. on Theory of Computing (STOC), pp. 407\u2013416. ACM, New York (2004)"},{"key":"9411_CR11","series-title":"LNCS","first-page":"752","volume-title":"Proc. of the 19th Annual International Symp. on Algorithms and Computation (ISAAC)","author":"H.N. Gabow","year":"2008","unstructured":"Gabow, H.N., Nie, S.: Finding long paths, cycles and circuits. In: Proc. of the 19th Annual International Symp. on Algorithms and Computation (ISAAC). LNCS, vol. 5369, pp. 752\u2013763. Springer, Berlin (2008)"},{"key":"9411_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979)"},{"key":"9411_CR13","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"key":"9411_CR14","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P.W. Goldberg","year":"1995","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2, 139\u2013152 (1995)","journal-title":"J. Comput. Biol."},{"key":"9411_CR15","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol.\u00a057. North-Holland, Amsterdam (2004)"},{"key":"9411_CR16","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamiltonian paths in grid graphs. SIAM J. Comput. 11, 676\u2013686 (1982)","journal-title":"SIAM J. Comput."},{"key":"9411_CR17","doi-asserted-by":"crossref","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 18, 82\u201398 (1997)","journal-title":"Algorithmica"},{"key":"9411_CR18","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"J.M. Keil","year":"1985","unstructured":"Keil, J.M.: Finding Hamiltonian circuits in interval graphs. Inf. Process. Lett. 20, 201\u2013206 (1985)","journal-title":"Inf. Process. Lett."},{"key":"9411_CR19","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H. M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: Hamiltonian circuits in chordal bipartite graphs. Discrete Math. 156, 291\u2013298 (1996)","journal-title":"Discrete Math."},{"key":"9411_CR20","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0020-0190(89)90038-0","volume":"32","author":"G. Narasimhan","year":"1989","unstructured":"Narasimhan, G.: A note on the Hamiltonian circuit problem on directed path graphs. Inf. Process. Lett. 32, 167\u2013170 (1989)","journal-title":"Inf. Process. Lett."},{"key":"9411_CR21","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0020-0190(88)90091-9","volume":"27","author":"G. Ramalingam","year":"1988","unstructured":"Ramalingam, G., Rangan, C. Pandu: A unified approach to domination problems on interval graphs. Inf. Process. Lett. 27, 271\u2013274 (1988)","journal-title":"Inf. Process. Lett."},{"key":"9411_CR22","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1093\/ietisy\/e91-d.2.170","volume":"91-D","author":"Y. Takahara","year":"2008","unstructured":"Takahara, Y., Teramoto, S., Uehara, R.: Longest path problems on Ptolemaic graphs. IEICE Trans. Inf. Syst. 91-D, 170\u2013177 (2008)","journal-title":"IEICE Trans. Inf. Syst."},{"key":"9411_CR23","series-title":"LNCS","first-page":"871","volume-title":"Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC)","author":"R. Uehara","year":"2004","unstructured":"Uehara, R., Uno, Y.: Efficient algorithms for the longest path problem. In: Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC). LNCS, vol. 3341, pp. 871\u2013883. Springer, Berlin (2004)"},{"key":"9411_CR24","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.ipl.2007.02.010","volume":"103","author":"R. Uehara","year":"2007","unstructured":"Uehara, R., Valiente, G.: Linear structure of bipartite permutation graphs and the longest path problem. Inf. Process. Lett. 103, 71\u201377 (2007)","journal-title":"Inf. Process. Lett."},{"key":"9411_CR25","first-page":"680","volume-title":"Proc. of the 11th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"S. Vishwanathan","year":"2000","unstructured":"Vishwanathan, S.: An approximation algorithm for finding a long path in Hamiltonian graphs. In: Proc. of the 11th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 680\u2013685. ACM, New York (2000)"},{"key":"9411_CR26","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.tcs.2007.02.012","volume":"377","author":"Z. Zhang","year":"2007","unstructured":"Zhang, Z., Li, H.: Algorithms for long paths in graphs. Theoret. Comput. Sci. 377, 25\u201334 (2007)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9411-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9411-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9411-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:05Z","timestamp":1559137505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9411-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,12]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["9411"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9411-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,12]]}}}