The Complexity of File Transfer Scheduling with Forwarding
Jennifer Whitehead · SIAM Journal on Computing · 1990
The file transfer scheduling problem was introduced and studied by Coffman, Garey, Johnson, and LaPaugh. This paper extends their model to include forwarding when no direct link exists between nodes. Several special cases of the problem, which were previously solvable by polynomial time algorithms, are shown to be NP-complete when forwarding is included. Other special cases are shown to continue to have polynomial time solutions in the forwarding model. All results assume the existence of a central controller.