Routing between Visible Vertices in Constrained Theta Graphs
Rodriguez, Jonathan
2021
-
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). It is not always viable, however, to know the whole network. For example, the network could be incredibly large, or the devices could be moving. Constantly ... read moreupdating the whole network can be very expensive, so we want to avoid this expense by using a limited amount of information at each node, namely just the neighbors. Introducing obstacles on the graph further increases the complexity of the problem.A good way to approach this problem is by using a family of graphs 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. Spiral Scan Routing, however, does require 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.
Advisor: Prof. Diane Souvaineread less - ID:
- np193q830
- To Cite:
- TARC Citation Guide EndNote
- Usage:
- Detailed Rights
