A Clustering Approach to the Bounded Diameter Minimum Spanning Tree Problem Using Ants

Open Access
Derr, Tyler Scott
Graduate Program:
Computer Science
Master of Science
Document Type:
Master Thesis
Date of Defense:
March 27, 2015
Committee Members:
  • Thang Nguyen Bui, Thesis Advisor
  • Ant-Based Optimization
  • Bounded Diameter Spanning Tree
  • Clustering
The bounded diameter minimum spanning tree problem is the problem of finding a minimum cost spanning tree of a graph such that the number of edges along the longest path in the tree is at most d. This problem is well known to be NP-hard. We present an ant-based algorithm for this problem in which we use two species of ants. The first species is used to discover clusters in the vertex set and then a bounded diameter spanning tree (BDST) is created within each cluster. The second species is then used to connect the cluster BDSTs together building a bounded diameter spanning tree for the whole graph. This tree is then locally optimized yielding a solution to the overall problem. Experimental tests have been conducted on two types of complete graphs, 135 Euclidean and 120 non-Euclidean, totalling 255 graphs. Each Euclidean graph consists of a set of vertices randomly placed in the unit square and the edge cost between two vertices is the Euclidean distance between them. The non-Euclidean graphs are structured such that all of the edge weights in the graph have been randomly selected from [0.01,0.99]. For the Euclidean graphs the results show that our algorithm achieves solutions close to the best known for most of the instances. However, on the non-Euclidean graphs our algorithm has obtained new best known solutions for the majority of the graphs and has come very close to the best known in the others.