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

scheduling algorithmpacket routing algorithmsarea-universal network

Mathematics Subject Classification ID

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

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

(21)

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

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)