Time-dependent shortest paths in bounded treewidth graphs

Glencora Borradaile, Morgan Shirley

We present a proof that the number of breakpoints in the arrival function between two terminals in graphs of treewidth $w$ is $n^{O({\log }^{2}w)}$ when the edge arrival functions are…