Efficient Parallel Algorithms For Core And Center Of A Tree Network

Location theory is concerned with optimal location of facilities on a given network, which can be seen as single points. However, in many real applications, the facility to be located is too large to be modeled as a point. That will call these kinds of facilities extensive facilities which have the form of a path or of a tree. Optimally locating a facility in a network is an important problem in the fields of transportation and communication. So, many researchers have paid their attention to these fields. The criteria for optimality extensively studied in the literature are the minimum eccentricity and the minimum distancesum criterion. The criteria for optimality extensively studied in the literature are the minimum eccentricity criterion in which the distance to the farthest vertex from the facility is minimized and the minimum distancesum criterion in which the total distance from the facility to the vertices is minimized.In this paper, we base on the minimum eccentricity and the minimum distancesum criterion of optimality criterions. We study these algorithms which are k-tree center, k-tree core, (k, l)-core and (k, l)-center of a tree network.Given a tree T, A k-tree center of T is a minimum eccentricity subtree of T, which contains exactly k leaves. A k-tree core of T is a minimum distancesum subtree of T, which contains exactly k leaves. We consider the problem of selecting a subtree with exactly k leaves and with a diameter of at most l, which minimizes the distance from the farthest vertex to the subtree. We call such a subtree the (k, l)-center of T. A subtree of T with at most k leaves and with a diameter of at most l which minimizes the sum of the distance of the vertices from the selected subtree, this subtree call a (k, l)-core of T. In this paper, we apply the Euler-tour technique, tree contraction and upward tree accumulation. We propose four efficient parallel algorithms to solve k-tree center,k-tree core, (k, l)-core and (k, l)-center of T,respectively. The algorithms we proposed take O(log n) time using O(n) work on the EREW PRAM. Furthennore, we study the properties of these questions. The algorithms of this paperimprove the algorithms of Wang proposed (Finding a fc-tree core and a /c-tree center of a tree network in parallel, IEEE Trans. Par. and Dis. Sys., 1998).