Routing Between Visible Vertices in Constrained Theta Graphs

Abstract

Undergraduate Thesis Defense:

Routing is the process of sending a message from a source vertex to a destination vertex in a network. When we have complete knowledge of the graph in advance, there are many algorithms that find the optimal path (e.g. Dijkstra, Bellman-Ford). However, it is not always viable to know the whole network. For example, the network could be incredibly large, or the devices could be moving. Constantly updating the whole network can be very expensive, so we want to avoid this by using a limited amount of information at each node, namely just the neighbors. The problem gets further complicated when we introduce obstacles on the graph.

A good way to approach this problem is by using a type of graph known as constrained Theta-graphs. We propose Spiral Scan Routing, the first competitive routing algorithm on Theta-(4k+2) graphs. This algorithm depends on the source and vertex being visible to each other, but it is deterministic and has a constant stretch factor. However, Spiral Scan Routing requires a message of size O(n) to be passed. We conclude by discussing ideas for improving this algorithm in order to reduce this space requirement.

Please join the meeting in Sococo VH 102, or Zoom.

Join Zoom Meeting: https://tufts.zoom.us/j/98610939077

PASSWORD: See colloquia email

Dial by your location: +1 646 558 8656 US (New York)

Meeting ID: 986 1093 9077

PASSCODE: See colloquia email