Improved Spanning and Routing Ratios on Geometric Graphs
Public Deposited- Resource Type
- Creator
- Abstract
In 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.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
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.
- Date Created
- 2019
Relations
- In Collection:
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
hill-improvedspanningandroutingratiosongeometric.pdf | 2023-05-05 | Public | Download |