Randomized Routing and Sorting on Fixed-Connection Networks

DOI10.1006/JAGM.1994.1030MaRDI QIDQ4304064zbMATH OpenOpenAlexFDO

Authors Bruce M. Maggs, Satish Rao, F. Thomson Leighton, Abhiram Ranade

Publication date 9 March 1995

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1994.1030

zbMATH Keywords

area-universal networkpacket routing algorithmsscheduling algorithm

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• Randomized multipacket routing and sorting on meshes
• Deterministic on-line routing on area-universal networks
• scientific article; zbMATH DE number 4049037
• k-k Routing, k-k Sorting, and Cut-Through Routing on the Mesh
• Optimal routing algorithms for mesh-connected processor arrays

Cited in

(23)

• Efficient delay routing
• Real-time emulations of bounded-degree networks
• Packet routing and PRAM emulation on star graphs and leveled networks
• Methods for message routing in parallel machines
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• FIFO and randomized competitive packet routing games
• Packet routing and selection on the POPS network
• Fast algorithms for bit-serial routing on a hypercube
• UNIVERSAL ROUTING AND PERFORMANCE ASSURANCE FOR DISTRIBUTED NETWORKS
• Simple Algorithms for Routing on Butterfly Networks with Bounded Queues
• Deterministic on-line routing on area-universal networks
• scientific article; zbMATH DE number 1775423 (Why is no real title available?)
• Improved deterministic PRAM simulation on the mesh
• A stochastic process on a network with connections to Laplacian systems of equations
• Train scheduling on a unidirectional path
• Improved algorithms for latency minimization in wireless networks
• A GENERAL PRAM SIMULATION SCHEME FOR CLUSTERED MACHINES
• On the benefit of supporting virtual channels in wormhole routers
• Routing with bounded buffers and hot-potato routing in vertex-symmetric networks
• Communication in parallel systems
• Randomized multipacket routing and sorting on meshes
• Store-and-forward multicast routing on the mesh
• Area-time tradeoffs for universal VLSI circuits

This page was built for publication: Randomized Routing and Sorting on Fixed-Connection Networks

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