An optimal time bound for oblivious routing

DOI10.1007/BF01840387MaRDI QIDQ908701zbMATH OpenFDO

Authors Ian Parberry

Publication date 1990

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

parallel machinesoblivious routingnetwork of processorsshuffle-exchange

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Theory of software (68N99)

Recommendations

• Optimal oblivious routing on \(d\)-dimensional meshes
• Tight bounds for oblivious routing in the hypercube
• Oblivious routing with limited buffer capacity
• Optimal oblivious routing in polynomial time
• A Time-Randomness Trade-Off for Oblivious Routing

Cites work

• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 4068238 (Why is no real title available?)
• A universal interconnection pattern for parallel computers
• Interconnections Between Processors and Memory Modules Using the Shuffle-Exchange Network
• On recurrent and recursive interconnection patterns
• Parallel Processing with the Perfect Shuffle
• Parallel permutation and sorting algorithms and a new generalized connection network
• Routing, merging, and sorting on parallel models of computation
• Some practical simulations of impractical parallel computers

Cited in

(12)

• Network-oblivious algorithms
• Survey on oblivious routing strategies
• Optimal oblivious routing in polynomial time
• scientific article; zbMATH DE number 1760014 (Why is no real title available?)
• Tight bounds for oblivious routing in the hypercube
• An O (log N ) deterministic packet-routing scheme
• scientific article; zbMATH DE number 1760011 (Why is no real title available?)
• Oblivious routing with limited buffer capacity
• Optimal oblivious routing in polynomial time
• scientific article; zbMATH DE number 7561477 (Why is no real title available?)
• Communication in parallel systems
• A Time-Randomness Trade-Off for Oblivious Routing

This page was built for publication: An optimal time bound for oblivious routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908701)