Two languages are more informative than one
Ido Dagan, Alon Itai, et al.
ACL 1991
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.
Ido Dagan, Alon Itai, et al.
ACL 1991
Steven L. Tanimoto, Alon Itai, et al.
Journal of the ACM
Alon Itai, Michael Rodeh
Information and Computation
David Bernstein, Michael Rodeh, et al.
IEEE TC