Previous | Next --- Slide 37 of 49
Back to Lecture Thumbnails
crow

There was an algorithms competition a year ago, about the task of sending "widgets" from any place in a city to any other place in a city (where locations in a city are represented as an undirected graph). There was a restriction that a widget had to travel along a path, and while the widget was on that path, no other widgets could use any of the edges along that path.

At the time, I thought this was a pretty unrealistic model, since it should be possible for other widgets to be using the a different edge on the same path at the same time. But now, I realize the whole competition was a circuit-switched routing problem in disguise -- if multiple routes are available from one endpoint in the network to another endpoint, which route will result in the least conflict.