You are invited to Tyler Derr's Master's Thesis defense.
Thesis Title: "A Clustering Approach to the Bounded Diameter Minimum Spanning Tree Problem Using Ants"
Thesis Advisor: Dr. Thang Bui
Date/Time: Friday, March 27, 2015, 1 pm
Location: Olmsted E309
Abstract
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 is created within each cluster. The second species is then used to connect the tree in the clusters together building a bounded diameter spanning tree for the whole graph. This tree is then local 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 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.
Thesis Title: "A Clustering Approach to the Bounded Diameter Minimum Spanning Tree Problem Using Ants"
Thesis Advisor: Dr. Thang Bui
Date/Time: Friday, March 27, 2015, 1 pm
Location: Olmsted E309
Abstract
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 is created within each cluster. The second species is then used to connect the tree in the clusters together building a bounded diameter spanning tree for the whole graph. This tree is then local 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 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.
No comments:
Post a Comment