Abstract
TRAFFIC-LIGHT SCHEDULING ON THE GRID
Discrete Applied Mathematics, Vol.53(1-3), pp.211-234
International Workshop on Broadcasting and Gossiping (SECHELT, CANADA, 01/Aug/1990 - 01/Aug/1990)
Sep/1994
Abstract
This paper studies the problem of route scheduling under the telephone model of communication networks. 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 d or less, using only one direction, scheduling is shown to require d + O(1) time. For simple routes using only two or three directions, scheduling is shown to require 2d + 3 and 2d + 4 time, respectively. Finally, for arbitrary simple routes scheduling is shown to require 2d + THETA(square-root d) time.
Details
- Title
- TRAFFIC-LIGHT SCHEDULING ON THE GRID
- Creators
- G KORTSARZ (null)David Peleg (null) - 972WIS_INST___83
- Resource Type
- Abstract
- Publication Details
- Discrete Applied Mathematics, Vol.53(1-3), pp.211-234; Sep/1994
- Number of pages
- 24
- Language
- English
- DOI
- https://doi.org/10.1016/0166-218X(94)90186-4
- Conference
- International Workshop on Broadcasting and Gossiping (SECHELT, CANADA, 01/Aug/1990 - 01/Aug/1990)
- Record Identifier
- 993262997203596
Metrics
4 Record Views