CS 269S, Fall 2012: Theory Seminar
Bren Hall, Room 1423, 1pm
November 2, 2012:

Algorithms for Graphs via Orthogonal Range Searching

Sergio Cabello

I will explain how orthogonal range searching has been useful to improve the running time of algorithms solving the following problems:
a) Computing the sum of the distances between all pairs of vertices in a graph of bounded treewidth.
b) Computing the dilation of a geometric graph of bounded treewidth.
c) Computing an optimal pricing in the Stackelberg shortest path tree game.

(Parts a) and b) are joint work with Christian Knauer.)