David Bernstein, Michael Rodeh, et al.
Journal of Algorithms
Consider k stations wishing to transmit messages over a network of channels to a common receiver. The capacity of a channel is the maximum amount of data which can be transmitted in a time unit. In addition to the transmission stations, the network contains switching nodes. Given that the jth station has σj messages (j = 1,..., k) to transmit, it is desired to find a schedule with minimum completion time T. The amount of data sent over a channel may vary in time. A schedule is stationary if the amount of data sent in a time unit is constant throughout the schedule. It is first shown that for every schedule there exists a stationary schedule with the same completion time. Thus, the search for an optimum schedule is confined to stationary schedules. The problem of finding an optimum stationary schedule is formulated as a multisource single-sink network flow problem, in which the net amount of outgoing flow from each source (transmission station) within one time unit is σj T. An O(k|E||V|2) time algorithm to find the minimum T similar to Dinic's flow algorithm is suggested. Using Sleator and Tarjan's techniques an O(k2|E||V|log|V|) algorithm is derived. The running time of both algorithms is independent of the σj's and the capacities. © 1985.
David Bernstein, Michael Rodeh, et al.
Journal of Algorithms
Michael Rodeh, Vaughan R. Pratt, et al.
Journal of the ACM
Alon Itai, Michael Rodeh
FOCS 1984
Alon Itai, Michael Rodeh
STOC 1977