Abstract
dc:description.abstractIn this thesis we examine a few classes of geometric graphs and improve the spanning and routing ratios on these graphs. We improve the routing ratio of the Delaunay triangulation from 5.90 to 3.56. We show that it is possible to route competitively on the Theta-4 graph with a routing ratio of 17. This bound on the routing ratio also serves to improve the bound on the spanning ratio from 237 to 17. We improve the spanning ratio of the convex hull of points arranged on the surface of a sphere from approximately 12.12 to 0.999 pi, and we improve the bound on the spanning ratio of the Theta-5 graph from 9.96 to 5.70.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy (Ph.D.)
- Level thesis:degree_level
- Doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- Carleton University
- Year dc:date.issued
- 2019
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Hill, Darryl Richard
Subjects
dc:subject × 1Rights
dc:rights- Statement dc:rights
-
- Copyright © 2019 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Language dc:language.iso
- en