A constrained minimum spanning tree problem ?
In this paper, we give an O(n2) algorithm for finding a point on a given line l which, if added to a given set of n points located on one side of l, will result in the minimum spanning tree. Scope and purpose The minimum spanning tree problem is one of the most important fundamental problems in combinatorial optimization. In this paper we consider a variant of such a problem which models a location problem. Given a line and a point set N located on one side of the line, the goal is to find just one point P on the line such that the minimum spanning tree for N?{P} is the shortest possible, which is denoted as the constrained minimum spanning tree problem (CMSTP). This problem has many applications in the real world such as transportation, communication, or location of some facilities. We apply the divide-and-conquer technique to reduce the complexity of our problem and provide an O(n2) algorithm.
90c27 68q25