{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T11:56:56Z","timestamp":1781092616121,"version":"3.54.1"},"reference-count":34,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["109-2221-E-845-001"],"award-info":[{"award-number":["109-2221-E-845-001"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["107-2115-M-845-001"],"award-info":[{"award-number":["107-2115-M-845-001"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:p>Given a complete graph [Formula: see text], with nonnegative edge costs, two subsets [Formula: see text] and [Formula: see text], a partition [Formula: see text] of [Formula: see text], [Formula: see text], [Formula: see text] and [Formula: see text] of [Formula: see text], [Formula: see text], a clustered Steiner tree is a tree [Formula: see text] of [Formula: see text] that spans all vertices in [Formula: see text] such that [Formula: see text] can be cut into [Formula: see text] subtrees [Formula: see text] by removing [Formula: see text] edges and each subtree [Formula: see text] spans all vertices in [Formula: see text], [Formula: see text]. The cost of a clustered Steiner tree is defined to be the sum of the costs of all its edges. A clustered selected-internal Steiner tree of [Formula: see text] is a clustered Steiner tree for [Formula: see text] if all vertices in [Formula: see text] are internal vertices of [Formula: see text]. The clustered selected-internal Steiner tree problem is concerned with the determination of a clustered selected-internal Steiner tree [Formula: see text] for [Formula: see text] and [Formula: see text] in [Formula: see text] with minimum cost. In this paper, we present the first known approximation algorithm with performance ratio [Formula: see text] for the clustered selected-internal Steiner tree problem, where [Formula: see text] is the best-known performance ratio for the Steiner tree problem.<\/jats:p>","DOI":"10.1142\/s0129054121500362","type":"journal-article","created":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T08:55:01Z","timestamp":1638262501000},"page":"55-66","source":"Crossref","is-referenced-by-count":2,"title":["The Clustered Selected-Internal Steiner Tree Problem"],"prefix":"10.1142","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0570-5865","authenticated-orcid":false,"given":"Yen Hung","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Taipei, No.1, Ai-Guo West Road, Taipei 100234, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2021,11,30]]},"reference":[{"key":"S0129054121500362BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.08.020"},{"key":"S0129054121500362BIB002","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1041"},{"key":"S0129054121500362BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"S0129054121500362BIB004","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281086"},{"key":"S0129054121500362BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"S0129054121500362BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/43.784119"},{"key":"S0129054121500362BIB007","doi-asserted-by":"publisher","DOI":"10.1002\/net.21713"},{"key":"S0129054121500362BIB008","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0255-1","volume-title":"Steiner Trees in Industry","author":"Cheng X.","year":"2001"},{"key":"S0129054121500362BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(75)90015-5"},{"key":"S0129054121500362BIB010","volume-title":"Introduction to Algorithm","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"S0129054121500362BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S1007-0214(07)70068-8"},{"key":"S0129054121500362BIB012","doi-asserted-by":"publisher","DOI":"10.1002\/net.20276"},{"key":"S0129054121500362BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3171-2"},{"key":"S0129054121500362BIB014","doi-asserted-by":"publisher","DOI":"10.1142\/6729"},{"key":"S0129054121500362BIB015","doi-asserted-by":"publisher","DOI":"10.1137\/0132072"},{"key":"S0129054121500362BIB016","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054114500051"},{"key":"S0129054121500362BIB017","volume-title":"Fundamentals of Molecular Evolution","author":"Graur D.","year":"2000","edition":"2"},{"key":"S0129054121500362BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010045"},{"key":"S0129054121500362BIB019","first-page":"448","volume-title":"Proc. 10th Ann. ACM\u2013SIAM Symp. Discrete Algorithms (SODA)","author":"Hougardy S.","year":"1999"},{"key":"S0129054121500362BIB020","doi-asserted-by":"publisher","DOI":"10.1002\/net.20100"},{"key":"S0129054121500362BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.035"},{"key":"S0129054121500362BIB022","series-title":"Annuals of Discrete Mathematics","volume-title":"The Steiner Tree Problem","volume":"53","author":"Hwang F. K.","year":"1992"},{"key":"S0129054121500362BIB023","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1968-037-0"},{"key":"S0129054121500362BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/BF00127356"},{"key":"S0129054121500362BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9301-8"},{"key":"S0129054121500362BIB026","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"S0129054121500362BIB027","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1086"},{"key":"S0129054121500362BIB028","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"S0129054121500362BIB029","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054120500367"},{"key":"S0129054121500362BIB030","first-page":"137","volume":"412","author":"Sekanina M.","year":"1960","journal-title":"Publ. Faculty of Science, University of Brno"},{"key":"S0129054121500362BIB031","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"},{"key":"S0129054121500362BIB032","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-014-9772-7"},{"key":"S0129054121500362BIB033","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"},{"key":"S0129054121500362BIB034","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90201-J"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121500362","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T10:26:33Z","timestamp":1699871193000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121500362"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,30]]},"references-count":34,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["10.1142\/S0129054121500362"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121500362","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,30]]}}}