{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T06:03:09Z","timestamp":1778824989385,"version":"3.51.4"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,1,2]],"date-time":"2019-01-02T00:00:00Z","timestamp":1546387200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s10878-018-00374-x","type":"journal-article","created":{"date-parts":[[2019,1,2]],"date-time":"2019-01-02T07:13:21Z","timestamp":1546413201000},"page":"165-184","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem"],"prefix":"10.1007","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7833-9520","authenticated-orcid":false,"given":"Mattia","family":"D\u2019Emidio","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Forlizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Frigioni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,1,2]]},"reference":[{"issue":"23","key":"374_CR1","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/j.ipl.2012.08.020","volume":"112","author":"X Bao","year":"2012","unstructured":"Bao X, Liu Z (2012) An improved approximation algorithm for the clustered traveling salesman problem. Inf Process Lett 112(23):908\u2013910","journal-title":"Inf Process Lett"},{"key":"374_CR2","doi-asserted-by":"crossref","unstructured":"Bil\u00f2 D, Grandoni F, Gual\u00e0 L, Leucci S, Proietti G (2015) Improved purely additive fault-tolerant spanners. In: Proceedings 23rd European symposium on algorithms (ESA), volume 9294 of Lecture notes in computer science. Springer, pp 167\u2013178","DOI":"10.1007\/978-3-662-48350-3_15"},{"key":"374_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund A, Husfeldt T, Kaski P, Koivisto M (2007) Fourier meets m\u00f6bius: fast subset convolution. In: Proceedings 39th ACM symposium on theory of computing (STOC). ACM, pp 67\u201374","DOI":"10.1145\/1250790.1250801"},{"issue":"1","key":"374_CR4","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka J, Grandoni F, Rothvo\u00df T, Sanit\u00e0 L (2013) Steiner tree approximation via iterative randomized rounding. J ACM 60(1):6","journal-title":"J ACM"},{"key":"374_CR5","volume-title":"Algorithms","author":"S Dasgupta","year":"2008","unstructured":"Dasgupta S, Papadimitriou CH, Vazirani U (2008) Algorithms, 1st edn. McGraw-Hill Inc, New York","edition":"1"},{"key":"374_CR6","unstructured":"D\u2019Emidio M, Forlizzi L, Frigioni D, Leucci S, Proietti G (2016) On the clustered shortest-path tree problem. In: Proceedings 17th Italian conference on theoretical computer science (ICTCS), volume 1720 of CEUR workshop proceedings, pp 263\u2013268"},{"key":"374_CR7","doi-asserted-by":"crossref","unstructured":"Fareed MS, Javaid N, Akbar M, Rehman S, Qasim U, Khan ZA (2012) Optimal number of cluster head selection for efficient distribution of sources in WSNs. In: Proceedings seventh international conference on broadband, wireless computing, communication and applications. IEEE, pp 626\u2013631","DOI":"10.1109\/BWCCA.2012.110"},{"issue":"1","key":"374_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(02)00404-6","volume":"148","author":"C Feremans","year":"2003","unstructured":"Feremans C, Labb\u00e9 M, Laporte G (2003) Generalized network design problems. Eur J Oper Res 148(1):1\u201313","journal-title":"Eur J Oper Res"},{"key":"374_CR9","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co, New York"},{"issue":"1","key":"374_CR10","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N Garg","year":"2000","unstructured":"Garg N, Konjevod G, Ravi R (2000) A polylogarithmic approximation algorithm for the group Steiner tree problem. J Algorithms 37(1):66\u201384","journal-title":"J Algorithms"},{"issue":"4","key":"374_CR11","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/s004530010045","volume":"28","author":"N Guttmann-Beck","year":"2000","unstructured":"Guttmann-Beck N, Hassin R, Khuller S, Raghavachari B (2000) Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28(4):422\u2013437","journal-title":"Algorithmica"},{"key":"374_CR12","doi-asserted-by":"crossref","unstructured":"Halperin E, Krauthgamer R (2003) Polylogarithmic inapproximability. In: Proceedings 35th ACM symposium on theory of computing (STOC), pp 585\u2013594","DOI":"10.1145\/780542.780628"},{"issue":"1","key":"374_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10878-014-9746-9","volume":"31","author":"C Lin","year":"2016","unstructured":"Lin C, Wu BY (2016) On the minimum routing cost clustered tree problem. J Comb Optim 31(1):1\u201316","journal-title":"J Comb Optim"},{"issue":"4","key":"374_CR14","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1109\/LCOMM.2008.071942","volume":"12","author":"C Sevgi","year":"2008","unstructured":"Sevgi C, Kocyigit A (2008) On determining cluster size of randomly deployed heterogeneous WSNs. IEEE Commun Lett 12(4):232\u2013234","journal-title":"IEEE Commun Lett"},{"key":"374_CR15","unstructured":"Wu BY, Lancia G, Bafna V, Chao K-M, Ravi R, Tang CY (1998) A polynomial time approximation scheme for minimum routing cost spanning trees. In: Proceedings 9th ACM-SIAM symposium on discrete algorithms (SODA), pp 21\u201332"},{"issue":"2","key":"374_CR16","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/s10878-014-9772-7","volume":"30","author":"BY Wu","year":"2015","unstructured":"Wu BY, Lin C (2015) On the clustered Steiner tree problem. J Comb Optim 30(2):370\u2013386","journal-title":"J Comb Optim"},{"key":"374_CR17","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2017.10.018","volume":"734","author":"P Zou","year":"2018","unstructured":"Zou P, Li H, Wang W, Xin C, Zhu B (2018) Finding disjoint dense clubs in a social network. Theor Comput Sci 734:15\u201323","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-00374-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-00374-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-00374-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T19:05:44Z","timestamp":1577905544000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-00374-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,2]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["374"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-00374-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,2]]},"assertion":[{"value":"2 January 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}