An optimal time bound for oblivious routing (Q908701): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q235683 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Giora Slutzki / rank | |||
Normal rank |
Revision as of 15:17, 11 February 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