Technical Report #97008 (October, 1997)

Single-Vehicle Scheduling Problem on a Tree with Depth-First Routing

by Hiroshi Nagamochi, Koji Mochizuki and Toshihide Ibaraki

In this paper, we first show that the TREE-VSP/DF with a home location $s$ has an optimal schedule that is independent of its start time, and that such schedule can be found in $O(n\log \Delta)$ time, where $\Delta$ is the maximum degree of tree $T$ and $n$ is the number of vertices. We then show that the minimum completion times $C(s')$ for all home locations $s'\in V$ can be simultaneously computed in $O(n)$ time, once the problem with a specified home location has been solved. We also consider the TREE-VSP/DF with a start vertex $s$ and a goal vertex $g$, and show that, once the TREE-VSP/DF with a specified home location $s$ has been solved, the minimum completion times $C(s,g)$ for all goal vertices $g\in V$ can be computed in $O(n)$ time.