Tight bounds for oblivious routing in the hypercube

DOI10.1007/BF02090400zbMath0731.68046MaRDI QIDQ3357537

Christos Kaklamanis, Thanasis Tsantilas, Danny Krizanc

Publication date: 1991

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

hypercuberoutinginterprocessor communication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Mathematical problems of computer architecture (68M07)

Related Items

Towards a better understanding of pure packet routing, Unnamed Item, Sparse Semi-Oblivious Routing: Few Random Paths Suffice, Oblivious Routing for Sensor Network Topologies, On the theory of interconnection networks for parallel computers, Parallel parsing of tree adjoining grammars on the connection machine, Survey on Oblivious Routing Strategies, Unnamed Item, Optimal oblivious routing on \(d\)-dimensional meshes, Optimal permutation routing for low-dimensional hypercubes, Fast algorithms for bit-serial routing on a hypercube, Some permutation routing algorithms for low-dimensional hypercubes, Optimal oblivious routing in polynomial time

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal time bound for oblivious routing
• Routing, merging, and sorting on parallel models of computation
• Décomposition de la somme cartesienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens
• Oblivious routing with limited buffer capacity
• Über drei kombinatorische Probleme am \(n\)-dimensionalen Würfel und Würfelgitter
• Efficient Schemes for Parallel Communication
• Efficient dispersal of information for security, load balancing, and fault tolerance
• A Scheme for Fast Parallel Communication