Article ID: | iaor1995947 |
Country: | Netherlands |
Volume: | 53 |
Issue: | 1/3 |
Start Page Number: | 211 |
End Page Number: | 234 |
Publication Date: | Sep 1994 |
Journal: | Discrete Applied Mathematics |
Authors: | Kortsarz Guy, Peleg David |
This paper studies the problem of route scheduling under the telephone model of communicationnetworks. Previous work in this model considered mostly the ‘broadcast’ and ‘gossip’ communication primitives. The approach studied here is that of devising simple, distributed universal schedules, that are efficient for wide families of routing instances, rather than attempting to solve individual instances separately. The paper concentrates on ‘traffic-light’ type schedules for route scheduling on the two-dimensional grid. In order to study the problem of scheduling given route instances, routes are classified according to the number of directions they use, and tight bounds are given on the time required for scheduling route instances in each class. For routes of length