{"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":1774455687618,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["2021R1F1A1048180"],"award-info":[{"award-number":["2021R1F1A1048180"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s11227-022-04768-x","type":"journal-article","created":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T16:03:24Z","timestamp":1661184204000},"page":"2783-2800","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Characterization of interval graphs that are paired 2-disjoint path coverable"],"prefix":"10.1007","volume":"79","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1052-5746","authenticated-orcid":false,"given":"Jung-Heum","family":"Park","sequence":"first","affiliation":[]},{"given":"Hyeong-Seok","family":"Lim","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,22]]},"reference":[{"issue":"3","key":"4768_CR1","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":"4768_CR2","doi-asserted-by":"crossref","unstructured":"Bondy JA, Murty USR (2008) Graph theory, 2nd printing","DOI":"10.1007\/978-1-84628-970-5"},{"issue":"4","key":"4768_CR3","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":"4768_CR4","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. Theoret Comput Sci 714:27\u201335","journal-title":"Theoret Comput Sci"},{"key":"4768_CR5","first-page":"209","volume":"93","author":"AM Dean","year":"1993","unstructured":"Dean AM (1993) The computational complexity of deciding Hamiltonian-connectedness. Congr Numer 93:209\u2013214","journal-title":"Congr Numer"},{"issue":"1","key":"4768_CR6","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. Discret Math 170(1):99\u2013106","journal-title":"Discret Math"},{"key":"4768_CR7","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of np-completeness"},{"key":"4768_CR8","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"},{"key":"4768_CR9","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, UK"},{"issue":"3","key":"4768_CR10","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1142\/S0129054120500148","volume":"31","author":"J Li","year":"2020","unstructured":"Li J, Melekian C, Zuo S, Cheng E (2020) Unpaired many-to-many disjoint path covers on bipartite $$k$$-ary $$n$$-cube networks with faulty elements. Int J Found Comput Sci 31(3):371\u2013383","journal-title":"Int J Found Comput Sci"},{"key":"4768_CR11","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. Theoret Comput Sci 677:1\u201311","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"4768_CR12","doi-asserted-by":"publisher","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. Discret Math Theor Comput Sci 16(2):125\u2013210","journal-title":"Discret Math Theor Comput Sci"},{"issue":"2","key":"4768_CR13","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. Discret Math 339(2):770\u2013779","journal-title":"Discret Math"},{"issue":"1","key":"4768_CR14","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"},{"issue":"8","key":"4768_CR15","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1142\/S0129054121500301","volume":"32","author":"H L\u00fc","year":"2021","unstructured":"L\u00fc H, Wu T (2021) Unpaired many-to-many disjoint path cover of balanced hypercubes. Int J Found Comput Sci 32(8):943\u2013956","journal-title":"Int J Found Comput Sci"},{"key":"4768_CR16","volume-title":"Algorithmic Graph Theory","author":"JA McHugh","year":"1990","unstructured":"McHugh JA (1990) Algorithmic Graph Theory. Prentice-Hall, New Jersey"},{"key":"4768_CR17","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2022.02.003","volume":"911","author":"R Niu","year":"2022","unstructured":"Niu R, Xu M (2022) The unpaired many-to-many $$k$$-disjoint paths in bipartite hypercube-like networks. Theoret Comput Sci 911:26\u201340","journal-title":"Theoret Comput Sci"},{"issue":"5","key":"4768_CR18","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 Software Eng 5(5):520\u2013529","journal-title":"IEEE Trans Software Eng"},{"issue":"10","key":"4768_CR19","first-page":"539","volume":"34","author":"JH Park","year":"2007","unstructured":"Park JH (2007) Conditions for disjoint path coverability in proper interval graphs. J KIISE: Comput Syst Theory 34(10):539\u2013554","journal-title":"J KIISE: Comput Syst Theory"},{"issue":"7","key":"4768_CR20","doi-asserted-by":"publisher","first-page":"6871","DOI":"10.1007\/s11227-020-03512-7","volume":"77","author":"JH Park","year":"2021","unstructured":"Park JH (2021) A sufficient condition for the unpaired $$k$$-disjoint path coverability of interval graphs. J Supercomput 77(7):6871\u20136888","journal-title":"J Supercomput"},{"key":"4768_CR21","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":"3","key":"4768_CR22","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1109\/TPDS.2006.37","volume":"17","author":"JH Park","year":"2006","unstructured":"Park JH, Kim HC, Lim HS (2006) Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements. IEEE Trans Parallel Distrib Syst 17(3):227\u2013240","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"4","key":"4768_CR23","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":"4768_CR24","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. Theoret Comput Sci 776:125\u2013137","journal-title":"Theoret Comput Sci"},{"key":"4768_CR25","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.tcs.2020.03.010","volume":"821","author":"JH Park","year":"2020","unstructured":"Park JH, Lim HS (2020) Characterization of interval graphs that are unpaired $$2$$-disjoint path coverable. Theoret Comput Sci 821:71\u201386","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"4768_CR26","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1002\/1097-0037(200103)37:2<102::AID-NET5>3.0.CO;2-S","volume":"37","author":"S Zhang","year":"2001","unstructured":"Zhang S, Wang Z (2001) Scattering number in graphs. Networks 37(2):102\u2013106","journal-title":"Networks"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04768-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-022-04768-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04768-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T12:16:58Z","timestamp":1673612218000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-022-04768-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,22]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["4768"],"URL":"https:\/\/doi.org\/10.1007\/s11227-022-04768-x","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,22]]},"assertion":[{"value":"10 August 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}