{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:41:04Z","timestamp":1771026064939,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T00:00:00Z","timestamp":1627344000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T00:00:00Z","timestamp":1627344000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["388221852"],"award-info":[{"award-number":["388221852"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this article we consider the Directed Steiner Path Cover problem on directed co-graphs. Given a directed graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$G=(V,E)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and a set <jats:inline-formula><jats:alternatives><jats:tex-math>$$T \\subseteq V$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>T<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of so-called terminal vertices, the problem is to find a minimum number of vertex-disjoint simple directed paths, which contain all terminal vertices and a minimum number of non-terminal vertices (Steiner vertices). The primary minimization criteria is the number of paths. We show how to compute in linear time a minimum Steiner path cover for directed co-graphs. This leads to a linear time computation of an optimal directed Steiner path on directed co-graphs, if it exists. Since the Steiner path problem generalizes the Hamiltonian path problem, our results imply the first linear time algorithm for the directed Hamiltonian path problem on directed co-graphs. We also give binary integer programs for the (directed) Hamiltonian path problem, for the (directed) Steiner path problem, and for the (directed) Steiner path cover problem. These integer programs can be used to minimize change-over times in pick-and-place machines used by companies in electronic industry.<\/jats:p>","DOI":"10.1007\/s10878-021-00781-7","type":"journal-article","created":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T21:02:32Z","timestamp":1627419752000},"page":"402-431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computing directed Steiner path covers"],"prefix":"10.1007","volume":"43","author":[{"given":"Frank","family":"Gurski","sequence":"first","affiliation":[]},{"given":"Dominique","family":"Komander","sequence":"additional","affiliation":[]},{"given":"Carolin","family":"Rehs","sequence":"additional","affiliation":[]},{"given":"Jochen","family":"Rethmann","sequence":"additional","affiliation":[]},{"given":"Egon","family":"Wanke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,27]]},"reference":[{"issue":"1","key":"781_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00454-013-9550-9","volume":"51","author":"AK Abu-Affash","year":"2014","unstructured":"Abu-Affash AK, Carmi P, Katz MJ, Segal M (2014) The Euclidean bottleneck Steiner path problem and other applications of ($$\\alpha $$,$$\\beta $$)-pair decomposition. Discrete Comput Geom 51(1):1\u201323","journal-title":"Discrete Comput Geom"},{"key":"781_CR2","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1002\/jgt.21775","volume":"77","author":"J Bang-Jensen","year":"2014","unstructured":"Bang-Jensen J, Maddaloni A (2014) Arc-disjoint paths in decomposable digraphs. J Graph Theory 77:89\u2013110","journal-title":"J Graph Theory"},{"key":"781_CR3","doi-asserted-by":"crossref","unstructured":"Bang-Jensen J, Gutin G (eds) (2018) Classes of directed graphs. Springer, Berlin","DOI":"10.1007\/978-3-319-71840-8"},{"key":"781_CR4","doi-asserted-by":"crossref","unstructured":"Bechet D, de\u00a0Groote P, Retor\u00e9 C (1997) A complete axiomatization of the inclusion of series-parallel partial orders. In: Rewriting techniques and applications, volume 1232 of LNCS, pp 230\u2013240. Springer 1997","DOI":"10.1007\/3-540-62950-5_74"},{"key":"781_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender HL, Cygan M, Kratsch S, Nederlof J (2015) Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf Comput 243:86\u2013111","journal-title":"Inf Comput"},{"key":"781_CR6","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.jda.2012.04.016","volume":"16","author":"M Chimani","year":"2012","unstructured":"Chimani M, Mutzel P, Zey B (2012) Improved Steiner tree algorithms for bounded treewidth. J Discrete Algorithms 16:67\u201378","journal-title":"J Discrete Algorithms"},{"key":"781_CR7","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil DG, Lerchs H, Stewart-Burlingham L (1981) Complement reducible graphs. Discrete Appl Math 3:163\u2013174","journal-title":"Discrete Appl Math"},{"issue":"1\u20133","key":"781_CR8","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/S0166-218X(01)00345-6","volume":"123","author":"Y Crama","year":"2002","unstructured":"Crama Y, van de Klundert J, Spieksma FCR (2002) Production planning problems in printed circuit board assembly. Discrete Appl Math 123(1\u20133):339\u2013361","journal-title":"Discrete Appl Math"},{"issue":"12","key":"781_CR9","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1016\/j.dam.2006.03.005","volume":"154","author":"C Crespelle","year":"2006","unstructured":"Crespelle C, Paul C (2006) Fully dynamic recognition algorithm and certificate for directed cographs. Discrete Appl Math 154(12):1722\u20131741","journal-title":"Discrete Appl Math"},{"key":"781_CR10","doi-asserted-by":"crossref","unstructured":"Custic A, Lendl S (2021) The Steiner cycle and path cover problem on interval graphs. J Comb Optim (To appear)","DOI":"10.1007\/s10878-021-00757-7"},{"issue":"5","key":"781_CR11","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"Fomin FV, Golovach PA, Lokshtanov D, Saurabh S (2010) Intractability of clique-width parameterizations. SIAM J Comput 39(5):1941\u20131956","journal-title":"SIAM J Comput"},{"issue":"3","key":"781_CR12","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1016\/j.ejc.2012.07.024","volume":"34","author":"R Ganian","year":"2013","unstructured":"Ganian R, Hlinen\u00fd P, Obdrz\u00e1lek J (2013) A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width. Eur J Comb 34(3):680\u2013701","journal-title":"Eur J Comb"},{"key":"781_CR13","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.dam.2013.10.038","volume":"168","author":"R Ganian","year":"2014","unstructured":"Ganian R, Hlinen\u00fd P, Kneis J, Langer A, Obdrz\u00e1lek J, Rossmanith P (2014) Digraph width measures in parameterized algorithmics. Discrete Appl Math 168:88\u2013107","journal-title":"Discrete Appl Math"},{"key":"781_CR14","doi-asserted-by":"publisher","first-page":"35","DOI":"10.19139\/soic.v5i1.260","volume":"5","author":"F Gurski","year":"2017","unstructured":"Gurski F (2017) Dynamic programming algorithms on directed cographs. Stat Optim Inf Comput 5:35\u201344","journal-title":"Stat Optim Inf Comput"},{"key":"781_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2015.11.003","volume":"616","author":"F Gurski","year":"2016","unstructured":"Gurski F, Wanke E, Yilmaz E (2016) Directed NLC-width. Theoret Comput Sci 616:1\u201317","journal-title":"Theoret Comput Sci"},{"issue":"4","key":"781_CR16","doi-asserted-by":"publisher","first-page":"87","DOI":"10.3390\/a12040087","volume":"12","author":"F Gurski","year":"2019","unstructured":"Gurski F, Komander D, Rehs C (2019) Oriented coloring on recursively defined digraphs. Algorithms 12(4):87","journal-title":"Algorithms"},{"key":"781_CR17","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/j.tcs.2020.11.047","volume":"855","author":"F Gurski","year":"2021","unstructured":"Gurski F, Komander D, Rehs C (2021) How to compute digraph width measures on directed co-graphs. Theoret Comput Sci 855:161\u2013185","journal-title":"Theoret Comput Sci"},{"key":"781_CR18","doi-asserted-by":"crossref","unstructured":"Gurski F, Hoffmann S, Komander D, Rehs C, Rethmann J, Wanke E (2020) Computing Directed Steiner path covers for directed co-graphs. In: Proceedings of the conference on current trends in theory and practice of computer science (SOFSEM), volume 12011 of LNCS, pp 556\u2013565. Springer","DOI":"10.1007\/978-3-030-38919-2_45"},{"key":"781_CR19","doi-asserted-by":"crossref","unstructured":"Gurski F, Hoffmann S, Komander D, Rehs C, Rethmann J, Wanke E (2020) Exact solutions for the Steiner path problem on special graph classes. In: Operations research proceedings (OR 2019), selected papers, pp 331\u2013338. Springer","DOI":"10.1007\/978-3-030-48439-2_40"},{"key":"781_CR20","doi-asserted-by":"crossref","unstructured":"Gurski F, Komander D, Rehs C (2019) Computing digraph width measures on directed co-graphs. In: Proceedings of international symposium on fundamentals of computation theory (FCT), volume 11651 of LNCS, pp 292\u2013305. Springer","DOI":"10.1007\/978-3-030-25027-0_20"},{"key":"781_CR21","doi-asserted-by":"crossref","unstructured":"Gurski F, Rehs C (2018) Directed path-width and directed tree-width of directed co-graphs. In: Proceedings of the international conference on computing and combinatorics (COCOON), volume 10976 of LNCS, pp 255\u2013267. Springer","DOI":"10.1007\/978-3-319-94776-1_22"},{"issue":"1","key":"781_CR22","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s00285-016-1084-3","volume":"75","author":"M Hellmuth","year":"2017","unstructured":"Hellmuth M, Stadler PF, Wieseke N (2017) The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations. J Math Biol 75(1):199\u2013237","journal-title":"J Math Biol"},{"key":"781_CR23","doi-asserted-by":"publisher","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 (1995) An optimal path cover algorithm for cographs. Comput Math Appl 30:75\u201383","journal-title":"Comput Math Appl"},{"issue":"5","key":"781_CR24","first-page":"11","volume":"76","author":"SS Moharana","year":"2013","unstructured":"Moharana SS, Joshi A, Vijay S (2013) Steiner path for trees. Int J Comput Appl 76(5):11\u201314","journal-title":"Int J Comput Appl"},{"key":"781_CR25","doi-asserted-by":"crossref","unstructured":"Nojgaard N, El-Mabrouk N, Merkle D, Wieseke N, Hellmuth M (2018) Partial homology relations\u2013satisfiability in terms of di-cographs. In: Proceedings of international computing and combinatorics conference (COCOON), volume 10976 of LNCS, pp 403\u2013415. Springer","DOI":"10.1007\/978-3-319-94776-1_34"},{"key":"781_CR26","first-page":"39","volume":"7","author":"L R\u00e9dei","year":"1934","unstructured":"R\u00e9dei L (1934) Ein kombinatorischer Satz. Acta Litteraria Szeged 7:39\u201343","journal-title":"Acta Litteraria Szeged"},{"key":"781_CR27","doi-asserted-by":"crossref","unstructured":"Reich G, Widmayer P (1990) Beyond Steiner\u2019s problem: a VLSI oriented generalization. In: Proceedings of graph-theoretical concepts in computer science (WG), volume 411 of LNCS, pp 196\u2013210. Springer","DOI":"10.1007\/3-540-52292-1_14"},{"key":"781_CR28","unstructured":"Wald JA, Colbourn CJ (1982) Steiner trees in outerplanar graphs. In: Thirteenth southeastern conference on combinatorics, graph theory, and computing, pp 15\u201322"},{"key":"781_CR29","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"JA Wald","year":"1983","unstructured":"Wald JA, Colbourn CJ (1983) Steiner trees, partial 2-trees, and minimum IFI networks. Networks 13:159\u2013167","journal-title":"Networks"},{"key":"781_CR30","unstructured":"Westbrook J, Yan D (1995) Approximation algorithms for the class Steiner tree problem. Research Report"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00781-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00781-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00781-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T18:32:55Z","timestamp":1646073175000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00781-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,27]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["781"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00781-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,27]]},"assertion":[{"value":"8 July 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2021","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 conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The datasets generated during and\/or analyzed during the current study are available from the corresponding author on reasonable request.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Availability of data and materials"}}]}}