Routing Between Visible Vertices in the Theta-10 Graph

December 10, 2020
2:00-3:00 pm ET
Sococo VH 209; Zoom
Speaker: Andrew Gonczi
Host: Diane Souvaine

Abstract

Routing is the problem of sending a message through a graph from a source- to a destination vertex. While this problem has classic solutions when the network is known (i.e.: Dijkstra's algorithm), it is sometimes unfeasible to have access to information about the entire graph. If the graph changes frequently, it is also hard to keep its representation up to date on anything but a local level (immediate neighbors of a vertex). This leads to the idea of local routing and using only a limited amount of memory (we call this 1-local O(1)-memory).

Geometric graphs are a family of graphs implicitly defined by geometric properties. One such graph is the Ɵ-graph. In the Ɵ-graph, the locations of vertices are fixed and the edges between vertices are weighted by the Euclidean distance between their endpoints. Previous results provided a routing strategy for a specific graph (Ɵ6 with constraints).

We introduce two more general approaches that works for two visible points in the constrained Ɵ4k+2 graph (k > 0). We then extend our approach to produce a 1-local O(1)-memory routing algorithm between any two points in the constrained Ɵ4k+2 graph.

This opens up the possibility for developing more competitive algorithms and leads to a couple of open questions: can we find tights bounds on the competitiveness of our first algorithm? And can we improve our second algorithm to being competitive?

Please join meeting in Sococo VH 209. Login: tuftscs.sococo.com

Join Zoom meeting: https://tufts.zoom.us/j/93132838976

Password: see colloquium email

Dial-in option not available.