{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T04:13:21Z","timestamp":1745381601069,"version":"3.40.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:00:00Z","timestamp":1743465600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:00:00Z","timestamp":1743465600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12361066","12361066"],"award-info":[{"award-number":["12361066","12361066"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12101593"],"award-info":[{"award-number":["12101593"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["buctrc202219"],"award-info":[{"award-number":["buctrc202219"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Project of Yunling Scholars Training of Yunnan Province","award":["K264202011820","K264202011820"],"award-info":[{"award-number":["K264202011820","K264202011820"]}]},{"name":"Project of Yunling Scholars Training of Yunnan Province","award":["K264202011820"],"award-info":[{"award-number":["K264202011820"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,4]]},"DOI":"10.1007\/s10878-025-01278-3","type":"journal-article","created":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T20:42:12Z","timestamp":1744404132000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for solving the heterogeneous rooted tree\/path cover problems"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5713-0867","authenticated-orcid":false,"given":"Pengxiang","family":"Pan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1385-8957","authenticated-orcid":false,"given":"Junran","family":"Lichen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ping","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1508-1440","authenticated-orcid":false,"given":"Jianping","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,11]]},"reference":[{"issue":"1\u20132","key":"1278_CR1","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0166-218X(95)00054-U","volume":"68","author":"I Averbakh","year":"1996","unstructured":"Averbakh I, Berman O (1996) A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree. Discret Appl Math 68(1\u20132):17\u201332","journal-title":"Discret Appl Math"},{"issue":"6","key":"1278_CR2","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1007\/s11590-015-0924-1","volume":"10","author":"J Bae","year":"2016","unstructured":"Bae J, Rathinam S (2016) A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem. Optim Lett 10(6):1269\u20131285","journal-title":"Optim Lett"},{"issue":"2","key":"1278_CR3","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1287\/trsc.1070.0209","volume":"42","author":"A Campbell","year":"2008","unstructured":"Campbell A, Vandenbussche D, Hermann W (2008) Routing for relief efforts. Transp Sci 42(2):127\u2013145","journal-title":"Transp Sci"},{"key":"1278_CR4","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie Mellon University"},{"issue":"1","key":"1278_CR5","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds J, Johnson EL (1973) Matching, Euler tours and the Chinese postman. Math Program 5(1):88\u2013124","journal-title":"Math Program"},{"issue":"4","key":"1278_CR6","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/j.orl.2003.11.010","volume":"32","author":"G Even","year":"2004","unstructured":"Even G, Garg N, Koemann J, Ravi R, Sinha A (2004) Min-max tree covers of graphs. Oper Res Lett 32(4):309\u2013315","journal-title":"Oper Res Lett"},{"key":"1278_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.disopt.2015.01.001","volume":"16","author":"B Farbstein","year":"2015","unstructured":"Farbstein B, Levin A (2015) Min-max cover of a graph with a small number of parts. Discret Optim 16:51\u201361","journal-title":"Discret Optim"},{"issue":"2","key":"1278_CR8","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/0207017","volume":"7","author":"GN Frederickson","year":"1978","unstructured":"Frederickson GN, Hecht MS, Kim CE (1978) Approximation algorithms for some routing problems. SIAM J Comput 7(2):178\u2013193","journal-title":"SIAM J Comput"},{"key":"1278_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-77778-8","volume-title":"The Vehicle Routing Problem: Latest Advances and New Challenges","author":"BL Golden","year":"2008","unstructured":"Golden BL, Raghavan S, Wasil EA (2008) The Vehicle Routing Problem: Latest Advances and New Challenges. Springer, New York"},{"issue":"1","key":"1278_CR10","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1287\/moor.2015.0729","volume":"41","author":"I G\u00f8rtz","year":"2016","unstructured":"G\u00f8rtz I, Molinaro M, Nagarajan V, Ravi R (2016) Capacitated vehicle routing with nonuniform speeds. Math Oper Res 41(1):318\u2013331","journal-title":"Math Oper Res"},{"key":"1278_CR11","doi-asserted-by":"crossref","unstructured":"Karlin A, Klein N, Oveis Gharan S (2021) A (slightly) improved approximation algorithm for metric TSP. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), Association for Computing Machinery, New York, USA, pp 32\u201345","DOI":"10.1145\/3406325.3451009"},{"key":"1278_CR12","doi-asserted-by":"crossref","unstructured":"Korte B, Vygen J (2018) Combinatorial Optimization: Theory and Algorithms. Springer","DOI":"10.1007\/978-3-662-56039-6"},{"key":"1278_CR13","doi-asserted-by":"publisher","first-page":"1335","DOI":"10.1093\/ietfec\/e88-a.5.1335","volume":"5","author":"H Nagamochi","year":"2005","unstructured":"Nagamochi H (2005) Approximating the minmax rooted-subtree cover problem. IEICE Trans Fundament Electr Commun Comput Sci 5:1335\u20131338","journal-title":"IEICE Trans Fundament Electr Commun Comput Sci"},{"key":"1278_CR14","doi-asserted-by":"crossref","unstructured":"Nagamochi H, Okada K (2003) Polynomial time 2-approximation algorithms for the minmax subtree cover problem. In: Proceedings of the 14th International Symposium on Algorithms and Computation, Springer, Heidelberg, pp 138\u2013147","DOI":"10.1007\/978-3-540-24587-2_16"},{"key":"1278_CR15","doi-asserted-by":"crossref","unstructured":"Pan P, Lichen J, Yang P, Li J (2023) The heterogeneous rooted tree cover problem. In: Proceedings of the 29th International Computing and Combinatorics Conference (COCOON 2023), Springer, pp 94\u2013105","DOI":"10.1007\/978-3-031-49193-1_8"},{"issue":"3","key":"1278_CR16","doi-asserted-by":"publisher","first-page":"1511","DOI":"10.1109\/TCNS.2020.2983791","volume":"7","author":"A Prasad","year":"2020","unstructured":"Prasad A, Choi HL, Sundaram S (2020) Min-max tours and paths for task allocation to heterogeneous agents. IEEE Trans Control Netw Syst 7(3):1511\u20131522","journal-title":"IEEE Trans Control Netw Syst"},{"issue":"8","key":"1278_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.112884","volume":"345","author":"S Schwartz","year":"2022","unstructured":"Schwartz S (2022) An overview of graph covering and partitioning. Discret Math 345(8):112884","journal-title":"Discret Math"},{"key":"1278_CR18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973594","volume-title":"Vehicle Routing: Problems","author":"P Toth","year":"2014","unstructured":"Toth P, Vigo D (2014) Vehicle Routing: Problems. Methods and Applications, MOS-SIAM, Philadelphia"},{"key":"1278_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-52824-9","volume-title":"Optimal Coverage in Wireless Sensor Networks","author":"W Wu","year":"2020","unstructured":"Wu W, Zhang Z, Lee W, Du D (2020) Optimal Coverage in Wireless Sensor Networks. Springer, Heidelberg"},{"issue":"3","key":"1278_CR20","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1109\/TC.2013.2295609","volume":"64","author":"W Xu","year":"2015","unstructured":"Xu W, Liang W, Lin X (2015) Approximation algorithms for min-max cycle cover problems. IEEE Trans Comput 64(3):600\u2013613","journal-title":"IEEE Trans Comput"},{"issue":"3","key":"1278_CR21","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.orl.2010.02.004","volume":"38","author":"Z Xu","year":"2010","unstructured":"Xu Z, Wen Q (2010) Approximation hardness of min-max tree covers. Oper Res Lett 38(3):169\u2013173","journal-title":"Oper Res Lett"},{"issue":"1","key":"1278_CR22","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s11590-010-0256-0","volume":"6","author":"S Yadlapalli","year":"2012","unstructured":"Yadlapalli S, Rathinam S, Darbha S (2012) 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem. Optim Lett 6(1):141\u2013152","journal-title":"Optim Lett"},{"key":"1278_CR23","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10878-018-0268-8","volume":"37","author":"W Yu","year":"2019","unstructured":"Yu W, Liu Z (2019) Better approximability results for min-max tree\/cycle\/path cover problems. J Comb Optim 37:563\u2013578","journal-title":"J Comb Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01278-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01278-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01278-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T07:55:50Z","timestamp":1745308550000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01278-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["1278"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01278-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,4]]},"assertion":[{"value":"4 March 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2025","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"}}],"article-number":"47"}}