{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T07:03:53Z","timestamp":1770966233515,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T00:00:00Z","timestamp":1764806400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T00:00:00Z","timestamp":1764806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12371352"],"award-info":[{"award-number":["12371352"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2026,2]]},"DOI":"10.1007\/s00373-025-02994-7","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T08:35:40Z","timestamp":1764837340000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithmic and structural results of directed Steiner path packing and directed path connectivity"],"prefix":"10.1007","volume":"42","author":[{"given":"Yuefang","family":"Sun","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2224-1484","authenticated-orcid":false,"given":"Xiaoyan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"2994_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, A.K., Carmi, P., Katz, M.J., Segal, M.: The Euclidean bottleneck Steiner path problem and other applications of $$(\\alpha , \\beta )$$-pair decomposition. Discrete Comput. Geom. 51, 1\u201323 (2014)","journal-title":"Discrete Comput. Geom."},{"issue":"4\/5","key":"2994_CR2","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/j.dam.2011.12.018","volume":"161","author":"M Aouchiche","year":"2013","unstructured":"Aouchiche, M., Hansen, P.: A survey of Nordhaus-Gaddum type relations. Discrete Appl. Math. 161(4\/5), 466\u2013546 (2013)","journal-title":"Discrete Appl. Math."},{"key":"2994_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-998-1","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J Bang-Jensen","year":"2009","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, London (2009)","edition":"2"},{"key":"2994_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-005-1188-4","volume":"45","author":"J Cheriyan","year":"2006","unstructured":"Cheriyan, J., Salavatipour, M.: Hardness and approximation results for packing Steiner trees. Algorithmica 45, 21\u201343 (2006)","journal-title":"Algorithmica"},{"key":"2994_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraphs homeomorphism problem. Theoret. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theoret. Comput. Sci."},{"key":"2994_CR6","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"2994_CR7","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02614374","volume":"78","author":"M Gr\u00f6tschel","year":"1997","unstructured":"Gr\u00f6tschel, M., Martin, A., Weismantel, R.: The Steiner tree packing problem in VLSI design. Math. Program. 78, 265\u2013281 (1997)","journal-title":"Math. Program."},{"key":"2994_CR8","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s10878-021-00781-7","volume":"43","author":"F Gurski","year":"2022","unstructured":"Gurski, F., Komander, D., Rehs, C., Rethmann, J., Wanke, E.: Computing directed Steiner path covers. J. Comb. Optim. 43, 402\u2013431 (2022)","journal-title":"J. Comb. Optim."},{"key":"2994_CR9","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.jco.2012.08.005","volume":"29","author":"C Huang","year":"2013","unstructured":"Huang, C., Lee, C., Gao, H., Hsieh, S.: The internal Steiner tree problem: Hardness and approximations. J. Complexity 29, 27\u201343 (2013)","journal-title":"J. Complexity"},{"issue":"2","key":"2994_CR10","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.: The disjoint paths problem in quadratic time. J. Combin. Theory Ser. B 102(2), 424\u2013435 (2012)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2994_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33828-6","volume-title":"Generalized Connectivity of Graphs","author":"X Li","year":"2016","unstructured":"Li, X., Mao, Y.: Generalized Connectivity of Graphs. Springer, Switzerland (2016)"},{"key":"2994_CR12","doi-asserted-by":"publisher","first-page":"2006","DOI":"10.1016\/j.dam.2012.04.006","volume":"160","author":"L Lipt\u00e1k","year":"2012","unstructured":"Lipt\u00e1k, L., Cheng, E., Kim, J., Kim, S.: One-to-many node-disjoint paths of hyper-star networks. Discrete Appl. Math. 160, 2006\u20132014 (2012)","journal-title":"Discrete Appl. Math."},{"key":"2994_CR13","doi-asserted-by":"crossref","unstructured":"Lu, P., Zhang, J., Poon, C.K., Cai, J.: Simulating undirected $$st$$-connectivity algorithms on uniform JAGs and NNJAGs, ISAAC, (2005), 767\u2013776","DOI":"10.1007\/11602613_77"},{"issue":"1","key":"2994_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.: Graph minors XIII: The disjoint paths problem. J. Combin. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2994_CR15","volume-title":"Algorithms for VLSI Physical Design Automation","author":"N Sherwani","year":"1999","unstructured":"Sherwani, N.: Algorithms for VLSI Physical Design Automation, 3rd edn. Kluwer Acad. Pub, London (1999)","edition":"3"},{"issue":"3","key":"2994_CR16","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1007\/s00373-021-02294-w","volume":"37","author":"Y Sun","year":"2021","unstructured":"Sun, Y., Gutin, G.: Strong subgraph connectivity of digraphs. Graphs Combin. 37(3), 951\u2013970 (2021)","journal-title":"Graphs Combin."},{"issue":"1","key":"2994_CR17","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/jgt.22437","volume":"92","author":"Y Sun","year":"2019","unstructured":"Sun, Y., Gutin, G., Yeo, A., Zhang, X.: Strong subgraph $$k$$-connectivity. J. Graph Theory 92(1), 5\u201318 (2019)","journal-title":"J. Graph Theory"},{"key":"2994_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2022.100745","volume":"46","author":"Y Sun","year":"2022","unstructured":"Sun, Y., Gutin, G., Zhang, X.: Packing strong subgraph in digraphs. Discrete Optim. 46, 100745 (2022)","journal-title":"Discrete Optim."},{"issue":"1","key":"2994_CR19","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1002\/jgt.22858","volume":"102","author":"Y Sun","year":"2023","unstructured":"Sun, Y., Yeo, A.: Directed Steiner tree packing and directed tree connectivity. J. Graph Theory 102(1), 86\u2013106 (2023)","journal-title":"J. Graph Theory"},{"issue":"1","key":"2994_CR20","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/0095-8956(80)90044-1","volume":"29","author":"TW Tillson","year":"1980","unstructured":"Tillson, T.W.: A Hamiltonian decomposition of $$K^*_{2m}$$, $$2m \\ge 8$$. J. Combin. Theory Ser. B 29(1), 68\u201374 (1980)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2994_CR21","unstructured":"Chuchu, Wang Yuefang, Sun (2024) Directed cycle k-connectivity of complete digraphs and complete regular bipartite digraphs Discrete Applied Mathematics 358203-213 10.1016\/j.dam.2024.07.024"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02994-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02994-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02994-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:04:52Z","timestamp":1770962692000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02994-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["2994"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02994-7","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]},"assertion":[{"value":"22 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2025","order":3,"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 no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"2"}}