کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
396142 | 666293 | 2007 | 18 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A factoring approach for the Steiner tree problem in undirected networks A factoring approach for the Steiner tree problem in undirected networks](/preview/png/396142.png)
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(|E|)O(|E|) algorithm is presented to find a minimum Steiner tree for series–parallel graphs where |E||E| is the number of edges. Based on this algorithm, we proposed an O(22c·|E|)O(22c·|E|) 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 |K||K|.
Journal: Information Sciences - Volume 177, Issue 12, 15 June 2007, Pages 2418–2435