{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T15:56:01Z","timestamp":1721922961852},"reference-count":23,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2007,9,4]],"date-time":"2007-09-04T00:00:00Z","timestamp":1188864000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2007,12]]},"abstract":"Abstract<\/jats:title>In this paper, we study a variant of the path cover problem, namely, the k<\/jats:italic>\u2010fixed\u2010endpoint path cover problem. Given a graph G<\/jats:italic> and a subset ${\\cal T}$<\/jats:styled-content> of k<\/jats:italic> vertices of V<\/jats:italic>(G<\/jats:italic>), a k<\/jats:italic>\u2010fixed\u2010endpoint path cover of G<\/jats:italic> with respect to ${\\cal T}$<\/jats:styled-content> is a set of vertex\u2010disjoint paths ${\\cal P}$<\/jats:styled-content> that covers the vertices of G<\/jats:italic> such that the k<\/jats:italic> vertices of ${\\cal T}$<\/jats:styled-content> are all endpoints of the paths in ${\\cal P}$<\/jats:styled-content>. The k<\/jats:italic>\u2010fixed\u2010endpoint path cover problem is to find a k<\/jats:italic>\u2010fixed\u2010endpoint path cover of G<\/jats:italic> of minimum cardinality; note that, if ${\\cal T}$<\/jats:styled-content> is empty, that is, k<\/jats:italic> = 0, the stated problem coincides with the classical path cover problem. We show that the k<\/jats:italic>\u2010fixed\u2010endpoint path cover problem can be solved in linear time on the class of cographs. More precisely, we first establish a lower bound on the size of a minimum k<\/jats:italic>\u2010fixed\u2010endpoint path cover of a cograph and prove structural properties for the paths of such a path cover. Then, based on these properties, we describe an algorithm which, for a cograph G<\/jats:italic> on n<\/jats:italic> vertices and m<\/jats:italic> edges, computes a minimum k<\/jats:italic>\u2010fixed\u2010endpoint path cover of G<\/jats:italic> in linear time, that is, in O<\/jats:italic>(n<\/jats:italic>+m<\/jats:italic>) time. The proposed algorithm is simple, requires linear space, and also enables us to solve some path cover related problems, such as the 1HP and 2HP, on cographs within the same time and space complexity. \u00a9 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 231\u2013240 2007<\/jats:p>","DOI":"10.1002\/net.20200","type":"journal-article","created":{"date-parts":[[2007,9,4]],"date-time":"2007-09-04T22:16:30Z","timestamp":1188944190000},"page":"231-240","source":"Crossref","is-referenced-by-count":8,"title":["A linear\u2010time algorithm for the k<\/i>\u2010fixed\u2010endpoint path cover problem on cographs"],"prefix":"10.1002","volume":"50","author":[{"given":"Katerina","family":"Asdre","sequence":"first","affiliation":[]},{"given":"Stavros D.","family":"Nikolopoulos","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,9,4]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"364","volume-title":"International Conference on Parallel Processing, Vol. III, Algorithms and Architecture","author":"Adhar G.S.","year":"1990"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90064-5"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes\u2014A survey, SIAM Monographs in Discrete Mathematics and Applications","author":"Brandst\u00e4dt A.","year":"1999"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90013-5"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90088-X"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90223-G"},{"key":"e_1_2_1_9_2","volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","author":"Garey M.R.","year":"1979"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.46298\/dmtcs.232","article-title":"On P\n 4\u2010tidy graphs","volume":"1","author":"Giakoumakis V.","year":"1997","journal-title":"Discrete Math Theor Comput Sci"},{"key":"e_1_2_1_11_2","unstructured":"C.Ho\u00e1ng Perfect graphs Ph.D. Thesis McGill University Montreal Canada 1985."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02253613"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.014"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.07.012"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.04.009"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.07.002"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90013-8"},{"key":"e_1_2_1_18_2","unstructured":"H.Lerchs On cliques and kernels Technical Report Department of Computer Science University of Toronto 1971."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(95)00139-P"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00319-7"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00068-3"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2003.08.004"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90123-B"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1093\/ietisy\/e89-d.10.2600"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20200","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20200","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T05:51:54Z","timestamp":1697608314000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20200"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,4]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["10.1002\/net.20200"],"URL":"https:\/\/doi.org\/10.1002\/net.20200","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,4]]}}}