{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T20:25:06Z","timestamp":1710361506411},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p> Given an edge-weighted undirected graph G = (V, E, c, w), where each edge e \u2208 E has a non-negative cost c(e) and a non-negative weight w(e), a set S \u2286 V of terminals and a positive constant D<jats:sub>0<\/jats:sub>, we seek a minimum cost Steiner tree in which all terminals appear as leaves and the tree diameter is bounded by D<jats:sub>0<\/jats:sub>. Here the tree diameter is the maximum weight of the paths connecting two different leaves in the tree. Such a problem is called the minimum cost diameter-constrained Steiner tree problem. The problem is NP-hard even when the topology of the Steiner tree is fixed. In present paper we focus on this fixed topology restricted version and present a fully polynomial time approximation scheme for computing a minimum cost diameter-constrained Steiner tree. <\/jats:p>","DOI":"10.1142\/s179383091100136x","type":"journal-article","created":{"date-parts":[[2012,1,4]],"date-time":"2012-01-04T19:00:28Z","timestamp":1325703628000},"page":"491-502","source":"Crossref","is-referenced-by-count":3,"title":["DIAMETER-CONSTRAINED STEINER TREES"],"prefix":"10.1142","volume":"03","author":[{"given":"WEI","family":"DING","sequence":"first","affiliation":[{"name":"Zhejiang Water Conservancy and Hydropower College, Hangzhou, Zhejiang, 310018, P. R. China"}]},{"given":"GUOHUI","family":"LIN","sequence":"additional","affiliation":[{"name":"Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada"}]},{"given":"GUOLIANG","family":"XUE","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287-8809, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.08.003"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.09.014"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1142\/9789812791450"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00285-0"},{"key":"rf6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.17.1.36"},{"key":"rf9","series-title":"Annals of Discrete Mathematics","volume-title":"The Steiner tree problem","volume":"53","author":"Hwang F. K.","year":"1992"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00227-2"},{"key":"rf14","first-page":"70","volume":"35","author":"Sahni S.","journal-title":"Oper. Res."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(96)00021-1"},{"key":"rf16","first-page":"359","volume":"215","author":"Wang L.","journal-title":"Theor. Comput. Sci."},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1119-9"},{"key":"rf18","first-page":"656","volume":"16","author":"Xue G.","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383091100136X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:40:43Z","timestamp":1565142043000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S179383091100136X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":15,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1142\/S179383091100136X"],"URL":"https:\/\/doi.org\/10.1142\/s179383091100136x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}