{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T09:32:40Z","timestamp":1649151160667},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2004,2]]},"abstract":"<jats:p> This paper addresses multicasting and broadcasting in undirected WDM networks and QoS extensions of multicasting. It is given an undirected network G=(V, E), with \u039b is the set of the available wavelengths in G, and associated with each edge, there is a subset of wavelengths on it. For a multicast request r=(s, D) with a source s and a set D of destinations, it is to find a tree rooted at s including all nodes in D such that the cost of the tree is minimized in terms of the cost of wavelength conversion at nodes and the cost of using wavelength on edges. This paper proves that multicasting in this model of networks is NP-Hard and cannot be approximated within a constant factor, unless P=NP. Furthermore, an auxiliary graph is constructed for the original WDM network, the multicasting is reduced to a group Steiner tree problem on the auxiliary graph and an approximate algorithm based on the group Steiner tree algorithm proposed by M. Charikar et al. with performance ratio of O( log <jats:sup>2<\/jats:sup>(nk) log log (nk) log p) is provided, where k=|\u039b| and p=|D\u222a{s}|. At last, some QoS extensions of multicasting are discussed. <\/jats:p>","DOI":"10.1142\/s0129054104002376","type":"journal-article","created":{"date-parts":[[2004,3,18]],"date-time":"2004-03-18T12:03:47Z","timestamp":1079611427000},"page":"187-203","source":"Crossref","is-referenced-by-count":0,"title":["MULTICASTING AND BROADCASTING IN UNDIRECTED WDM NETWORKS AND QoS EXTENTIONS OF MULTICASTING"],"prefix":"10.1142","volume":"15","author":[{"given":"YINLONG","family":"XU","sequence":"first","affiliation":[{"name":"National High Performance Computing Center at Hefei, Department of Computer Science and Technology, University of Science and Technology of China, 230087, Hefei, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"LI","family":"LIN","sequence":"additional","affiliation":[{"name":"National High Performance Computing Center at Hefei, Department of Computer Science and Technology, University of Science and Technology of China, 230087, Hefei, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GUOLIANG","family":"CHEN","sequence":"additional","affiliation":[{"name":"National High Performance Computing Center at Hefei, Department of Computer Science and Technology, University of Science and Technology of China, 230087, Hefei, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YINGYU","family":"WAN","sequence":"additional","affiliation":[{"name":"National High Performance Computing Center at Hefei, Department of Computer Science and Technology, University of Science and Technology of China, 230087, Hefei, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WEIJUN","family":"GUO","sequence":"additional","affiliation":[{"name":"National High Performance Computing Center at Hefei, Department of Computer Science and Technology, University of Science and Technology of China, 230087, Hefei, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00137-6"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1109\/49.510913"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1109\/49.552065"},{"key":"rf6","volume-title":"Computers and intractability: a guide to the theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf7","volume-title":"Fiber-optical Networks","author":"Green P. E.","year":"1992"},{"key":"rf8","volume-title":"Tech. Rep. TR-97-03","author":"Haberman B. K.","year":"1997"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00090-0"},{"key":"rf10","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1109\/26.905896","volume":"49","author":"Jia X. H.","journal-title":"IEEE Trans. on Communications"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1109\/90.234851"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1109\/90.779211"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1109\/90.720901"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52292-1_14"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1109\/49.564132"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1109\/49.12889"},{"key":"rf19","volume-title":"Tech. Rep. ICSI TR-94-024","author":"Widyono R.","year":"1994"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054104002376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:25:57Z","timestamp":1565191557000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054104002376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,2]]},"references-count":16,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2004,2]]}},"alternative-id":["10.1142\/S0129054104002376"],"URL":"https:\/\/doi.org\/10.1142\/s0129054104002376","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,2]]}}}