The Information Collection Network Construction Problem

In this thesis,we consider the information collection network constructon problem,which is a generalization of the capacitated network design problem.It is defined as follows:given a weighted undirected graph G =(V,E;w;t;B),where a length function w:E→R+,a.sink vertex t ∈ V,a set of sources saying S ＝V\{t},and the length of the stock piece B is L,and its capacity is U,and for all edge e ∈ E,w(e)≤ L,the capacity of each edge is at most ·U.It is asked to use such stock pieces to construct a subnetwork of graph G,such that a unit information from each source in S is transported to the sink t,satisfying the fact that the capacity of each edge of the subnetwork N dose not exceed k · U.The objective is to minimize the number of stock pieces used,saying k(K).To solve this problem,we design two approximation algorithms,called an algorith-m CLCN-1 and an algorithm CLCN-2,where the approximation ratios of CLCN-1 algorithm and CLCN-2 algorithm are 4 and 7/2,whose time complexity are 0(n3).