Routing in Geometric Graphs

Abstract

A fundamental problem in computer science is that of finding a path in a graph. When the whole graph is available, standard pathfinding algorithms can be applied such as Depth-First Search or Dijkstra's Algorithm. However, the problem of finding a path is more challenging in an online setting when at every step of the computation, only local information is available to the routing algorithm (such as the neighbourhood of the current vertex in the path). The difficulty is in deciding which edge to follow with only this local information.

We will explore different techniques for finding a path in a graph in the online setting with an emphasis on finding pathsin geometric graphs (graphs whose vertices are points in the plane and whose edges are segments between these points). We will highlight the difficulties involved with routing in this setting and review some of the currently best-known routing algorithms in this setting.

Bio:

Prosenjit Bose received his B. Math (1990) and M. Math (1991) in Computer Science and Combinatorics from the University of Waterloo, Canada. He completed his Ph.D. (1995) in Computer Science at McGill University, Canada, where he received the D.W. Ambridge Award as the outstanding Ph.D. graduate. In 1995, he was a Killam/NSERC Postdoctoral Fellow at UBC and in 1996, he was an assistant professor in the department of Math and Computer Science at l'Universite du Quebec a Trois- Rivieres. Since 1997, he has been at Carleton University, Canada. Currently, he is a Full Professor at the School of Computer Science. He has received several research and teaching awards. His main research area is Computational Geometry. He has published close to 200 journal and 200 conference papers in the area.

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