{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:26:16Z","timestamp":1747189576232,"version":"3.40.5"},"reference-count":27,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:p> In this paper, we consider the problem of covering the vertex set of a given graph by [Formula: see text] trees so as to minimize the maximum weight of the trees, as a subproblem of the multi-ferry scheduling problem proposed by Zhao and Ammar. After pointing out that the approximation ratio of a greedy scheme based on the Kruskal\u2019s algorithm is provably bad, we show that the approximation ratio cannot be better than 3\/2 for [Formula: see text] even when the edge selection criterion is modified so as to minimize the increase in the maximum weight in the collection of trees. We then propose two polynomial-time algorithms with a guaranteed approximation ratio. The first algorithm achieves 3-approximation for the class of graphs in which the edge weights satisfy the triangle inequality. The second algorithm achieves 4-approximation for any connected graph with arbitrary edge weights. <\/jats:p>","DOI":"10.1142\/s0129054123500235","type":"journal-article","created":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T08:03:01Z","timestamp":1700208181000},"page":"841-856","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Minimum k-Tree Cover of a Connected Graph Inspired by the Multi-Ferry Routing in Delay Tolerant Networks"],"prefix":"10.1142","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9412-7309","authenticated-orcid":false,"given":"Fujita","family":"Satoshi","sequence":"first","affiliation":[{"name":"Department of Information Engineering, Hiroshima University, Kagamiyama 1-4-1, Higashi-Hiroshima, 739-8527, Japan"}]}],"member":"219","published-online":{"date-parts":[[2023,11,16]]},"reference":[{"key":"S0129054123500235BIB001","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2841192"},{"key":"S0129054123500235BIB002","doi-asserted-by":"publisher","DOI":"10.1109\/AINA.2017.75"},{"key":"S0129054123500235BIB003","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.2017.8254434"},{"key":"S0129054123500235BIB004","first-page":"171","volume-title":"Proc. IEEE International Conference on Communications","author":"Chen T. W.","year":"1998"},{"volume-title":"Proc. Symposium on on New Directions and Recent Results in Algorithms and Complexity","year":"1976","author":"Christofides N.","key":"S0129054123500235BIB005"},{"volume-title":"Proc. IEEE Symposium on Wireless Personal Mobile Communications","year":"2001","author":"Clausen T.","key":"S0129054123500235BIB006"},{"key":"S0129054123500235BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00340-8"},{"key":"S0129054123500235BIB008","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"Garey M. R.","key":"S0129054123500235BIB009"},{"key":"S0129054123500235BIB010","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0848"},{"key":"S0129054123500235BIB011","first-page":"117","volume":"87","author":"Guttmann-Beck N.","year":"1998","journal-title":"Appl. Math."},{"key":"S0129054123500235BIB012","doi-asserted-by":"publisher","DOI":"10.1109\/AINA.2010.162"},{"key":"S0129054123500235BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-585-29603-6_5"},{"key":"S0129054123500235BIB014","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451009"},{"key":"S0129054123500235BIB015","doi-asserted-by":"publisher","DOI":"10.1109\/ICOIN.2015.7057961"},{"key":"S0129054123500235BIB016","series-title":"Lecture Notes in Computer Science","volume-title":"Service Assurance with Partial and Intermittent Resources. SAPIR 2004","volume":"3126","author":"Lindgren A."},{"key":"S0129054123500235BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/BF01193336"},{"key":"S0129054123500235BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"S0129054123500235BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/190809.190336"},{"key":"S0129054123500235BIB020","doi-asserted-by":"publisher","DOI":"10.1109\/MCSA.1999.749281"},{"key":"S0129054123500235BIB021","doi-asserted-by":"publisher","DOI":"10.1109\/ETCS.2010.350"},{"key":"S0129054123500235BIB022","doi-asserted-by":"publisher","DOI":"10.1109\/HPCC.and.EUC.2013.175"},{"key":"S0129054123500235BIB023","doi-asserted-by":"publisher","DOI":"10.1109\/IAEAC.2017.8054297"},{"key":"S0129054123500235BIB024","doi-asserted-by":"publisher","DOI":"10.1109\/ICCSN.2009.44"},{"key":"S0129054123500235BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00335-1"},{"key":"S0129054123500235BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(96)00155-5"},{"key":"S0129054123500235BIB027","first-page":"308","volume-title":"Proc. IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS 2003)","author":"Zhao W.","year":"2003"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123500235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T05:44:50Z","timestamp":1730094290000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123500235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,16]]},"references-count":27,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["10.1142\/S0129054123500235"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123500235","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,11,16]]}}}