{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:55:28Z","timestamp":1787500528348,"version":"build-2736575974"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,12,16]],"date-time":"2009-12-16T00:00:00Z","timestamp":1260921600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2010,3]]},"DOI":"10.1007\/s11786-009-0004-y","type":"journal-article","created":{"date-parts":[[2009,12,15]],"date-time":"2009-12-15T02:19:00Z","timestamp":1260843540000},"page":"85-96","source":"Crossref","is-referenced-by-count":3,"title":["An Optimal Algorithm for the k-Fixed-Endpoint Path Cover on Proper Interval Graphs"],"prefix":"10.1007","volume":"3","author":[{"given":"George B.","family":"Mertzios","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,12,16]]},"reference":[{"issue":"1","key":"4_CR1","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/S0097539700372216","volume":"31","author":"P. Hell","year":"2001","unstructured":"Hell P., Shamir R., Sharan R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput. 31(1), 289\u2013305 (2001)","journal-title":"SIAM J. Comput."},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Hsu, W.L.: A simple test for interval graphs. In: WG \u201992: Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 11\u201316. Springer, London (1993)","DOI":"10.1007\/3-540-56402-0_31"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"D. Corneil","year":"1995","unstructured":"Corneil D., Kim H., Natarajan S., Olariu S., Sprague A.P.: Simple linear time recognition of unit interval graphs. Inf. Process. Lett. 55, 99\u2013104 (1995)","journal-title":"Inf. Process. Lett."},{"key":"4_CR4","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: The ultimate interval graph recognition algorithm? In: SODA \u201998: Proceedings of the ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 175\u2013180 (1998)"},{"issue":"3","key":"4_CR5","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0020-0190(03)00298-9","volume":"87","author":"B.S. Panda","year":"2003","unstructured":"Panda B.S., Das S.K.: A linear time recognition algorithm for proper interval graphs. Inf. Process. Lett. 87(3), 153\u2013161 (2003)","journal-title":"Inf. Process. Lett."},{"key":"4_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511542985","volume-title":"Tolerance Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic M.C., Trenk A.N.: Tolerance Graphs. Cambridge University Press, Cambridge (2004)"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"A.V. Carrano Establishing the order to human chromosome-specific DNA fragments. In: Woodhead, A.D., Barnhart, B.J. (eds.) Biotechnology and the Human Genome, pp. 37\u201350. Plenum Press, New York (1988)","DOI":"10.1007\/978-1-4684-5547-2_5"},{"key":"4_CR8","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. W.H. Freeman, San Francisco (1979)"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Gupta, U.I., Lee, D.T., Leung, J.Y.T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks 459\u2013467 (1982)","DOI":"10.1002\/net.3230120410"},{"issue":"5","key":"4_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(92)90216-I","volume":"43","author":"J.Y. Hsiao","year":"1992","unstructured":"Hsiao J.Y., Tang C.Y.: An efficient algorithm for finding a maximum weight 2-independent set on interval graphs. Inf. Process. Lett. 43(5), 229\u2013235 (1992)","journal-title":"Inf. Process. Lett."},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Chang, M.S., Peng, S.L., Liaw, J.L.: Deferred-query\u2014an efficient approach for problems on interval and circular-arc graphs (extended abstract). In: WADS, pp. 222\u2013233 (1993)","DOI":"10.1007\/3-540-57155-8_250"},{"issue":"3","key":"4_CR12","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., Rangan C.P.: Linear algorithm for optimal path cover problem on interval graphs. Inf. Process. Lett. 35(3), 149\u2013153 (1990)","journal-title":"Inf. Process. Lett."},{"key":"4_CR13","unstructured":"Adhar, G.S., Peng, S.: Parallel algorithms for path covering hamiltonian path and hamiltonian cycle in cographs. In: International Conference on Parallel Processing, vol. 3, pp. 364\u2013365 (1990)"},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0898-1221(95)00139-P","volume":"30","author":"R. Lin","year":"1995","unstructured":"Lin R., Olariu S., Pruesse G.: An optimal path cover algorithm for cographs. Comput. Math. Appl. 30, 75\u201383 (1995)","journal-title":"Comput. Math. Appl."},{"key":"4_CR15","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/0304-3975(93)90123-B","volume":"115","author":"R. Srikant","year":"1993","unstructured":"Srikant R., Sundaram R., Singh K.S., Rangan C.P.: Optimal path cover problem on block graphs and bipartite permutation graphs. Theor. Comput. Sci. 115, 351\u2013357 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR16","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-comlete. SIAM J. Comput. 5, 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"key":"4_CR17","volume-title":"Algorithmic Graph Theory and Perfect Graphs, vol. 57. Annals of Discrete Mathematics","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Annals of Discrete Mathematics. Amsterdam, The Netherlands (2004)"},{"key":"4_CR18","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":"4_CR19","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(86)90135-3","volume":"23","author":"A.A. Bertossi","year":"1986","unstructured":"Bertossi A.A., Bonucelli M.A.: Finding hamiltonian circuits in interval graph generalizations. Inf. Process. Lett. 23, 195\u2013200 (1986)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"4_CR20","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.dam.2005.07.002","volume":"154","author":"R.W. Hung","year":"2006","unstructured":"Hung R.W., Chang M.S.: Solving the path cover problem on circular-arc graphs by using an approximation algorithm. Discrete Appl. Math. 154(1), 76\u2013105 (2006)","journal-title":"Discrete Appl. Math."},{"key":"4_CR21","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":"4_CR22","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1002\/net.20200","volume":"50","author":"K. Asdre","year":"2007","unstructured":"Asdre K., Nikolopoulos S.D.: A linear-time algorithm for the k-fixed-endpoint path cover problem on cographs. Networks 50, 231\u2013240 (2007)","journal-title":"Networks"},{"key":"4_CR23","unstructured":"Asdre, K., Nikolopoulos, S.D.: A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs. In: 18th International Conference on Combinatorial Algorithms (IWOCA\u201907), Newcastle, Australia (2007)"},{"issue":"4","key":"4_CR24","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/j.aml.2007.04.001","volume":"21","author":"G.B. Mertzios","year":"2008","unstructured":"Mertzios G.B.: A matrix characterization of interval and proper interval graphs. Appl. Math. Lett. 21(4), 332\u2013337 (2008)","journal-title":"Appl. Math. Lett."}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-009-0004-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-009-0004-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-009-0004-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T18:32:27Z","timestamp":1559413947000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-009-0004-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,16]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["4"],"URL":"https:\/\/doi.org\/10.1007\/s11786-009-0004-y","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,16]]}}}