Back to search

University of British Columbia

Ant colony optimization and rectilinear Steiner minimal trees

Abstract

dc:description

This paper consists of two distinct parts. In the first part, we introduce the Rectilinear Steiner Minimal Tree (RSMT) problem and describe the Ant Colony algorithm which we use to construct the RSMT. The development of an Ant Colony algorithm called AntCol Steiner is described and we create a working program of the algorithm using the Sun Microsystems Java programming language (see appendix A to H for details). We investigate the effectiveness of our algorithm by using AntCol Steiner to construct; and draw RSMT a given a random set of terminals. In the second part, we look at an application of the Kirchoff's Matrix Tree theorem. We find the length of a Rectilinear Minimal Spanning Tree (RMST) spanning a set of random terminals. We verify the accuracy of our results from the Kirchoff's Matrix Tree algorithm using Prim's RMST Algorithm. Our original plan was to develop an algorithm based on this theorem to determine the length of a RSTM. However, we were unable to modify the algorithm we used to find the length of the RMST, for the case of a RSMT.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Blackman, Anthony Curtis

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/17733

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Blackman, Anthony Curtis. Ant colony optimization and rectilinear Steiner minimal trees. master's thesis, University of British Columbia, 2006. http://hdl.handle.net/2429/17733