Abstract
Finding the optimal location of a facility on a network is a real and significant problem in our daily life. It has been widely investigated by researchers of various fields, especially in the fields of transportation and communication. The criteria for optimality discussed extensively in the literature are distance-sum and eccentricity. The distance-sum of a facility is the total distance from all vertices to it. The eccentricity of a facility is the distance from the farthest vertex to it. Due to the variety of facility kinds and different criteria for optimality, many location problems have been defined and studied. The reasons why we are interested in this kind of problems are as follows. 1) It is a real and important problem. 2) Many location problems have not been solved efficiently so far. 3) There are still many problems without efficient parallel algorithms. Most of location problems are NP-Hard on general graphs, such as the problems of locating p-median, locating tree-shaped median, and locating minimum distance-sum path of a specified length. Thus, investigators focus on some special classes of graphs. Trees get the most attention. In this thesis, all problems are discussed on trees. We have several the following results. First, we propose efficient algorithms to improve upper bounds for many well-known location problems. For examples, we improve the upper bound for the problem of finding a core of a specified length from O(n2) time to O(nlog nloglog n) time, the upper bound for the problem of finding a length-constrained heaviest path from O(nlog2 n) time to O(nlog n) time, and the upper bound for the problem of finding a 2-median on an unweighted tree from O(nlog n) time to O(n) time. Secondly, we provide W(nlog n) lower bounds for two problems that are encountered frequently in the designing of several location problems. Thirdly, we define a problem called the integral f-left match problem and provide it an O(n) time algorithm. The proposed algorithm can be applied to solve many location problems on unweighted trees in O(n) time.