A Time-Randomness Trade-Off for Oblivious Routing

DOI10.1137/0219017MaRDI QIDQ3468611zbMATH OpenOpenAlexFDO

Authors Eli Upfal, David Peleg

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219017

zbMATH Keywords

communication networkspermutation routingrandomized algorithmsresource trade-off

Mathematics Subject Classification ID

Theory of software (68N99) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• An optimal time bound for oblivious routing
• Mixing times and \(\ell_p\) bounds for oblivious routing
• On improving optimal oblivious routing
• Optimal oblivious routing in polynomial time
• Optimal oblivious routing in polynomial time
• Oblivious routing in directed graphs with random demands
• Randomness vs. time in anonymous networks
• Randomized Throughput-Optimal Oblivious Routing for Torus Networks
• Oblivious routing with limited buffer capacity

Cited in

(9)

• Quasi-random rumor spreading: reducing randomness can be costly
• A time-randomness tradeoff for quasi-random rumour spreading
• scientific article; zbMATH DE number 5855082 (Why is no real title available?)
• How much can hardware help routing?
• On the theory of interconnection networks for parallel computers
• Time-Randomness Trade-offs in Parallel Computation
• Safe and efficient traffic laws for mobile robots
• Bounds on tradeoffs between randomness and communication complexity
• An optimal time bound for oblivious routing

This page was built for publication: A Time-Randomness Trade-Off for Oblivious Routing

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