An optimal time bound for oblivious routing (Q908701): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:34, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An optimal time bound for oblivious routing |
scientific article |
Statements
An optimal time bound for oblivious routing (English)
0 references
1990
0 references
The routing problem is the problem of routing n data packets in a network of n processors. Usually, such a network is assumed to be constant- degree, i.e. each processor is connected to a constant number of other processors. A routing scheme is oblivious if the route taken by each packet depends only on its source and destination. Previous results by Borodin, Hopcroft and Lang show that oblivious routing can be done optimally in \(\theta\) (\(\sqrt{n})\) time. The author considers the case when more than n processors are available; more precisely, he shows that if p processors are available, then oblivious routing can be done in \(\theta\) (n/\(\sqrt{p}+\log n)\) time. Applications of these results are also given.
0 references
network of processors
0 references
parallel machines
0 references
shuffle-exchange
0 references
oblivious routing
0 references