Routing in the Theta-graph

Abstract

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: https://tufts.zoom.us/j/93398033179

Password: see colloquium email

Dial-in option not available for this talk.