Routing in the Theta-graph

April 29, 2021
3:00-4:00 pm ET
Sococo VH 402, Zoom
Speaker: Andrew Gonczi
Host: Diane Souvaine


Quals talk:

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 work 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.

Join meeting in Sococo VH 402, or Zoom.

Join Zoom meeting:

Password: see colloquium email

Dial-in option not available for this talk.