Routing on Heavy Path WSPD Spanners

Creator:

Tuttle, Tyler James

2020

Abstract:

In this thesis, we present a construction of a spanner on a set of $n$ points in $\R^d$ that we call a heavy path WSPD spanner. The construction is parameterized by a constant $s>2$. The size of the graph is $O(s^dn)$ and the spanning ratio is at most $1+2/s+2/(s-1)$. We also show that this graph has a hop spanning ratio of at most $2\lg{n}+1$. We present a memoryless local routing algorithm for heavy path WSPD spanners. A vertex $v$ of the graph stores $O(\deg(v)\log{n})$ bits of information. The routing ratio is at most $1+4/s+1/(s-1)$ and at least $1+4/s$. The number of edges on the routing path is bounded by $2\lg{n}+1$. We then show that the construction and routing algorithm can be generalized to metric spaces of bounded doubling dimension. The spanning and hop spanning ratios are unchanged. The routing ratio becomes at most $1+(2+\frac{\tau}{\tau-1})/s+1/(s-1)$, where $\tau\ge11$ is a constant.

Computer Science

English

Publisher:

Carleton University

Thesis Degree Name:

Master of Computer Science:
M.C.S.

Master's

Computer Science

Parent Collection:

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).