Converter placement supporting broadcast in WDM optical networks
文献类型：期刊论文
| 作者 | Ruan, L; Du, DZ; Hu, XD ; Jia, XH; Li, DY; Sun, Z
|
| 刊名 | IEEE TRANSACTIONS ON COMPUTERS
 |
| 出版日期 | 2001-07-01 |
| 卷号 | 50期号:7页码:750-758 |
| 关键词 | network optimization optical networks WDM converter placement Color-Covering Vertex Color-Covering |
| ISSN号 | 0018-9340 |
| 英文摘要 | Given a WDM optical network with wavelength channels on its fiber links, we consider the problem of finding the minimum set of network nodes such that, with wavelength converters at these nodes, broadcast can be supported in the network. We call this problem the Converter Placement problem. We model a given network using a graph G with colors on its edges and give a mathematical formulation for the problem based on the graph model. Two related problems, Color-Covering and Vertex Color-Covering, are given and analyzed. Both of them are shown to have a polynomial-time approximation with performance ratio In n + 1 and Inn is the best possible performance ratio unless NP subset of DTIME(n(polylogn)), where n is the number of vertices in G. Using these results, we show that the Converter Placement problem has a polynomial-time approximation with performance ratio 2(ln n + 1) and (1)/(2)ln n is the best possible performance ratio unless NP subset of DTIME(n(polylogn)). We present an approximation algorithm to solve the Converter Placement problem and study the performance of the algorithm on randomly generated network topologies. |
| WOS研究方向 | Computer Science ; Engineering |
| 语种 | 英语 |
| WOS记录号 | WOS:000169945400011 |
| 出版者 | IEEE COMPUTER SOC |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/16668]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Ruan, L |
| 作者单位 | 1.Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA 2.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China 3.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China 4.City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China 5.Shandong Univ, Sch Math & Syst Sci, Jinan 250100, Peoples R China |
| 推荐引用方式 GB/T 7714 | Ruan, L,Du, DZ,Hu, XD,et al. Converter placement supporting broadcast in WDM optical networks[J]. IEEE TRANSACTIONS ON COMPUTERS,2001,50(7):750-758. |
| APA | Ruan, L,Du, DZ,Hu, XD,Jia, XH,Li, DY,&Sun, Z.(2001).Converter placement supporting broadcast in WDM optical networks.IEEE TRANSACTIONS ON COMPUTERS,50(7),750-758. |
| MLA | Ruan, L,et al."Converter placement supporting broadcast in WDM optical networks".IEEE TRANSACTIONS ON COMPUTERS 50.7(2001):750-758. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。