標題: A factoring approach for the Steiner tree problem in undirected networks
作者: Wang, Chu-Fu
Jan, Rong-Hong
資訊工程學系
Department of Computer Science
關鍵字: Steiner tree problem;multicast routing;network optimization;two-terminal series-parallel graph
公開日期: 15-六月-2007
摘要: 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.
URI: http://dx.doi.org/10.1016/j.ins.2007.01.014
http://hdl.handle.net/11536/10683
ISSN: 0020-0255
DOI: 10.1016/j.ins.2007.01.014
期刊: INFORMATION SCIENCES
Volume: 177
Issue: 12
起始頁: 2418
結束頁: 2435
顯示於類別:期刊論文


文件中的檔案:

  1. 000246595100003.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。