Abstract
Consider a set of communication posts on a large plane. Each post isequipped with a transmitter that can reach some distance t from the post.If all the posts are within distance t of each other, all can communicatewithout difficulty. Suppose, however, that some posts are further than tunits apart. We would like to know if the posts can be split into twogroups so that within each group each pair of posts may communicate. Inorder to conserve energy, we wish to reduce the power of the transmittersas much as possible. Accordingly, what is the smallest t for which such apartition into two group is possible﹖The above problem is typical of a large class of problems that have beenstudied reccntly, that concern the clustering of a set of objects. Theproblem of clustering a set of objects arises in many disciplines, forexample, data compression, pattern recognition and service siteassignment. Because of the wide range of applications, there are manyvariations of this problem. The main difference between these problems isin the objective function. Many different objective functions have beenconsidered by many researchers. These objective functions usually dependon the dissimilarity between any two objects.Generally speaking, the clustering problem is to partition a set of nobjects into k nonempty disjoint subsets, called clusters. Manycomputational complexities have been discovered for different clusteringproblems. Since many clustering problems, when k>=3 have been proved to beNP- complete, we concentrate on the clustering problems when k=2, or2- clustering problems.In this dissertation, we discuss the following 2- clustering problems: thedual satisfaction problem, the farthest pair partition problem, theconstrained farthest pair partition problem, minimum diameter partitionproblem, the specified diameter partition problem and the Euclideanmini- sum 2- clustering problem.The first three problems are defined and solved on the graph model. Wepropose a uniform approach, called the spanning tree vertex labelingapproach, to partition the input vertex set into two disjoint subsets.Essentially, we construct a minimum, or maximum spanning tree, dependingupon the problem. We then partition the vertices based upon the treeconstructed. Our approach is easier to understand and easier to implement.The last three problems are discussed on Euclidean plane. that is, theinput of the problem is a set of points in 2- dimensional plane. Wediscover some geometric properties that can be used to find the optimalsolution efficiently. The geometric properties are developtd by using theconcept of maximum spanning tree of points. We found that the reason thatwe can devise more better algorithms than others is we do not consider somany pairs of points. In fact, we only consider those pairs of points thatrelated to the maximum spanning tree of points.