Browsing by Author "Wang, Chu-Fu"

Now showing 1 - 2 of 2

A factoring approach for the Steiner tree problem in undirected networks
(2007-06-15)
Wang, Chu-Fu
;
Jan, Rong-Hong
;
資訊工程學系
;
Department of Computer Science
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.
An Upper Bound of the Throughput for Multi-Radio Wireless Mesh Networks
(2010-08-01)
Jan, Rong-Hong
;
Huang, Shu-Ying
;
Wang, Chu-Fu
;
資訊工程學系
;
Department of Computer Science
This paper focuses on how to determine an upper bound of maximum throughput from mesh clients to the Internet (or from the Internet to mesh clients) for multi-radio Wireless Mesh Networks (WMNs) under an interference-free assumption. In the case of the number of channels for assignment being high enough in a multi-radio WMN to meet the interference-free assumption, then the resulting solution can provide the basis for channel assignment and routing to achieve optimal throughput.