A factoring approach for the Steiner tree problem in undirected networks
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
2435 | en_US |
dc.citation.issue |
12 | en_US |
dc.citation.spage |
2418 | en_US |
dc.citation.volume |
177 | en_US |
dc.citation.woscount |
2 | |
dc.contributor.author |
Wang, Chu-Fu | en_US |
dc.contributor.author |
Jan, Rong-Hong | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2014-12-08T15:13:50Z | |
dc.date.available |
2014-12-08T15:13:50Z | |
dc.date.issued |
2007-06-15 | en_US |
dc.description.abstract |
In communication networks, many applications, such as video on demand and video conferencing, must establish a communications tree that spans a subset K in a vertex set. The source node can then send identical data to all nodes in set K along this tree. This kind of communication is known as multicast communication. A network optimization problem, called the Steiner tree problem (STP), is presented to find a least cost multicasting tree. In this paper, an O(vertical bar E vertical bar) algorithm is presented to find a minimum Steiner tree for series-parallel graphs where vertical bar E vertical bar is the number of edges. Based on this algorithm, we proposed an O(2(2c) . vertical bar E vertical bar) algorithm to solve the Steiner tree problem for general graphs where c is the number of applied factoring procedures. The c value is strongly related to the topology of a given graph. This is quite different from other algorithms with exponential time complexities in vertical bar K vertical bar. (c) 2007 Elsevier Inc. All rights reserved. | en_US |
dc.identifier.doi |
10.1016/j.ins.2007.01.014 | en_US |
dc.identifier.issn |
0020-0255 | en_US |
dc.identifier.journal |
INFORMATION SCIENCES | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/j.ins.2007.01.014 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/10683 | |
dc.identifier.wosnumber |
WOS:000246595100003 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Steiner tree problem | en_US |
dc.subject |
multicast routing | en_US |
dc.subject |
network optimization | en_US |
dc.subject |
two-terminal series-parallel graph | en_US |
dc.title |
A factoring approach for the Steiner tree problem in undirected networks | en_US |
dc.type |
Article | en_US |
檔案
- 000246595100003.pdf (1.63 MB, Adobe PDF)
所屬典藏: 期刊論文