{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T16:21:27Z","timestamp":1774455687606,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["2018R1D1A1B07045566"],"award-info":[{"award-number":["2018R1D1A1B07045566"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002648","name":"Catholic University of Korea","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002648","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s11227-020-03512-7","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T14:09:23Z","timestamp":1609769363000},"page":"6871-6888","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A sufficient condition for the unpaired k-disjoint path coverability of interval graphs"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1052-5746","authenticated-orcid":false,"given":"Jung-Heum","family":"Park","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"issue":"3","key":"3512_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0020-0190(90)90064-5","volume":"35","author":"SR Arikati","year":"1990","unstructured":"Arikati SR, Rangan CP (1990) Linear algorithm for optimal path cover problem on interval graphs. Inf Process Lett 35(3):149\u2013153","journal-title":"Inf Process Lett"},{"issue":"3","key":"3512_CR2","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s00453-009-9292-5","volume":"58","author":"K Asdre","year":"2010","unstructured":"Asdre K, Nikolopoulos SD (2010) The 1-fixed-endpoint path cover problem is polynomial on interval graphs. Algorithmica 58(3):679\u2013710","journal-title":"Algorithmica"},{"key":"3512_CR3","doi-asserted-by":"crossref","unstructured":"Bondy JA, Murty USR (2008) Graph theory, 2nd printing","DOI":"10.1007\/978-1-84628-970-5"},{"issue":"3","key":"3512_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth KS, Lueker GS (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J Comput Syst Sci 13(3):335\u2013379","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"3512_CR5","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1002\/jgt.21832","volume":"79","author":"H Broersma","year":"2015","unstructured":"Broersma H, Fiala J, Golovach PA, Kaiser T, Paulusma D, Proskurowski A (2015) Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs. J Graph Theory 79(4):282\u2013299","journal-title":"J Graph Theory"},{"key":"3512_CR6","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2017.12.006","volume":"714","author":"H Cao","year":"2018","unstructured":"Cao H, Zhang B, Zhou Z (2018) One-to-one disjoint path covers in digraphs. Theor Comput Sci 714:27\u201335","journal-title":"Theor Comput Sci"},{"key":"3512_CR7","unstructured":"Corneil DG, Olariu S, Stewart L (1998) The ultimate interval graph recognition algorithm? In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 175\u2013180"},{"issue":"1\u20133","key":"3512_CR8","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 (1993) Paths in interval graphs and circular arc graphs. Discrete Math 112(1\u20133):49\u201364","journal-title":"Discrete Math"},{"issue":"1","key":"3512_CR9","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0012-365X(95)00359-5","volume":"170","author":"JS Deogun","year":"1997","unstructured":"Deogun JS, Kratsch D, Steiner G (1997) 1-tough cocomparability graphs are hamiltonian. Discrete Math 170(1):99\u2013106","journal-title":"Discrete Math"},{"key":"3512_CR10","first-page":"90","volume":"24","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of np-completeness. SIAM Rev 24:90","journal-title":"SIAM Rev"},{"key":"3512_CR11","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"Gilmore PC, Hoffman AJ (1964) A characterization of comparability graphs and of interval graphs. Can J Math 16:539\u2013548","journal-title":"Can J Math"},{"issue":"1\u20132","key":"3512_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"Habib M, McConnell R, Paul C, Viennot L (2000) Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor Comput Sci 234(1\u20132):59\u201384","journal-title":"Theor Comput Sci"},{"key":"3512_CR13","doi-asserted-by":"publisher","DOI":"10.1201\/9781420044829","volume-title":"Graph theory and interconnection networks","author":"LH Hsu","year":"2008","unstructured":"Hsu LH, Lin CK (2008) Graph theory and interconnection networks. CRC Press, Boca Raton"},{"issue":"5","key":"3512_CR14","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1016\/j.aml.2010.11.030","volume":"24","author":"RW Hung","year":"2011","unstructured":"Hung RW, Chang MS (2011) Linear-time certifying algorithms for the path cover and hamiltonian cycle problems on interval graphs. Appl Math Lett 24(5):648\u2013652","journal-title":"Appl Math Lett"},{"issue":"4","key":"3512_CR15","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"JM Keil","year":"1985","unstructured":"Keil JM (1985) Finding hamiltonian circuits in interval graphs. Inf Process Lett 20(4):201\u2013206","journal-title":"Inf Process Lett"},{"issue":"5","key":"3512_CR16","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1080\/00207160.2012.656614","volume":"89","author":"JH Lee","year":"2012","unstructured":"Lee JH, Park JH (2012) General-demand disjoint path covers in a graph with faulty elements. Int J Comput Math 89(5):606\u2013617","journal-title":"Int J Comput Math"},{"key":"3512_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.03.008","volume":"677","author":"J Li","year":"2017","unstructured":"Li J, Wang G, Chen L (2017) Paired 2-disjoint path covers of multi-dimensional torus networks with $$2n-3$$ faulty edges. Theor Comput Sci 677:1\u201311","journal-title":"Theor Comput Sci"},{"issue":"2","key":"3512_CR18","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.tcs.2015.03.012","volume":"16","author":"P Li","year":"2015","unstructured":"Li P, Wu Y (2015) Spanning connectedness and hamiltonian thickness of graphs and interval graphs. Discrete Math Theor Comput Sci 16(2):125\u2013210","journal-title":"Discrete Math Theor Comput Sci"},{"issue":"1","key":"3512_CR19","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/140981265","volume":"31","author":"P Li","year":"2017","unstructured":"Li P, Wu Y (2017) A linear time algorithm for the 1-fixed-endpoint path cover problem on interval graphs. SIAM J Discrete Math 31(1):210\u2013239","journal-title":"SIAM J Discrete Math"},{"issue":"2","key":"3512_CR20","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1016\/j.disc.2015.10.021","volume":"339","author":"HS Lim","year":"2016","unstructured":"Lim HS, Kim HC, Park JH (2016) Ore-type degree conditions for disjoint path covers in simple graphs. Discrete Math 339(2):770\u2013779","journal-title":"Discrete Math"},{"issue":"1","key":"3512_CR21","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/s11227-018-02734-0","volume":"75","author":"H L\u00fc","year":"2019","unstructured":"L\u00fc H (2019) Paired many-to-many two-disjoint path cover of balanced hypercubes with faulty edges. J Supercomput 75(1):400\u2013424","journal-title":"J Supercomput"},{"key":"3512_CR22","volume-title":"Algorithmic graph theory","author":"JA McHugh","year":"1990","unstructured":"McHugh JA (1990) Algorithmic graph theory. Prentice-Hall, New Jersey"},{"issue":"5","key":"3512_CR23","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1109\/TSE.1979.234213","volume":"5","author":"SC Ntafos","year":"1979","unstructured":"Ntafos SC, Hakimi SL (1979) On path cover problems in digraphs and applications to program testing. IEEE Trans Softw Eng 5(5):520\u2013529","journal-title":"IEEE Trans Softw Eng"},{"issue":"3","key":"3512_CR24","doi-asserted-by":"publisher","first-page":"115","DOI":"10.5626\/JCSE.2018.12.3.115","volume":"12","author":"JH Park","year":"2018","unstructured":"Park JH (2018) Paired many-to-many 3-disjoint path covers in bipartite toroidal grids. J Comput Sci Eng 12(3):115\u2013126","journal-title":"J Comput Sci Eng"},{"key":"3512_CR25","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.dam.2015.12.002","volume":"205","author":"JH Park","year":"2016","unstructured":"Park JH, Choi J, Lim HS (2016) Algorithms for finding disjoint path covers in unit interval graphs. Discrete Appl Math 205:132\u2013149","journal-title":"Discrete Appl Math"},{"key":"3512_CR26","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ipl.2018.10.010","volume":"142","author":"JH Park","year":"2019","unstructured":"Park JH, Ihm I (2019) A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph. Inf Process Lett 142:57\u201363","journal-title":"Inf Process Lett"},{"issue":"4","key":"3512_CR27","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1109\/TC.2008.160","volume":"58","author":"JH Park","year":"2009","unstructured":"Park JH, Kim HC, Lim HS (2009) Many-to-many disjoint path covers in the presence of faulty elements. IEEE Trans Comput 58(4):528\u2013540","journal-title":"IEEE Trans Comput"},{"key":"3512_CR28","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.tcs.2019.01.019","volume":"776","author":"JH Park","year":"2019","unstructured":"Park JH, Kim JH, Lim HS (2019) Disjoint path covers joining prescribed source and sink sets in interval graphs. Theor Comput Sci 776:125\u2013137","journal-title":"Theor Comput Sci"},{"key":"3512_CR29","first-page":"139","volume-title":"Proof techniques in graph theory","author":"FS Roberts","year":"1969","unstructured":"Roberts FS (1969) Indifference graphs. In: Harary F (ed) Proof techniques in graph theory. Academic Press, New York, pp 139\u2013146"},{"issue":"8","key":"3512_CR30","doi-asserted-by":"publisher","first-page":"5583","DOI":"10.1007\/s11227-019-02817-6","volume":"75","author":"F Wang","year":"2019","unstructured":"Wang F, Zhao W (2019) One-to-one disjoint path covers in hypercubes with faulty edges. J Supercomput 75(8):5583\u20135595","journal-title":"J Supercomput"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03512-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-020-03512-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03512-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,10]],"date-time":"2022-12-10T11:29:37Z","timestamp":1670671777000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-020-03512-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":30,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["3512"],"URL":"https:\/\/doi.org\/10.1007\/s11227-020-03512-7","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"16 November 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}