A fast parallel algorithm for routing in permutation networks

DOI10.1109/TC.1981.6312171zbMath0455.94047OpenAlexW2089828587MaRDI QIDQ3904540

G. Lev, Nicholas J. Pippenger, Leslie G. Valiant

Publication date: 1981

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tc.1981.6312171

zbMATH Keywords

randomizationinterconnection networks

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Stochastic network models in operations research (90B15) Deterministic network models in operations research (90B10) Applications of graph theory to circuits and networks (94C15)

Related Items (28)

Routing, merging, and sorting on parallel models of computation ⋮ Asymmetrical multiconnection three‐stage clos networks ⋮ Off‐line permutation routing on circuit‐switched fixed‐routing networks ⋮ Improved edge-coloring with three colors ⋮ The probabilistic method yields deterministic parallel algorithms ⋮ Solving fundamental problems on sparse-meshes ⋮ The local nature of \(\Delta\)-coloring and its algorithmic applications ⋮ Parallel algorithms for routing in nonblocking networks ⋮ Parallel O(log n) time edge-colouring of trees and Halin graphs ⋮ Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs ⋮ The generalized folding-cube network ⋮ Minimum multiplicity edge coloring via orientation ⋮ Applications of matching and edge‐coloring algorithms to routing in clos networks ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ Optimally edge-colouring outerplanar graphs is in NC ⋮ Counterexample to a conjecture of Szymanski on hypercube routing ⋮ A complexity theory of efficient parallel algorithms ⋮ Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem ⋮ A parallel algorithm for approximating the minimum cycle cover ⋮ Multicommodity flows in simple multistage networks ⋮ Approximating matchings in parallel ⋮ Parallel random access machines with bounded memory wordsize ⋮ Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings ⋮ A parallel-design distributed-implementation (PDDI) general-purpose computer ⋮ On permutations of wires and states ⋮ Restricted CRCW PRAMs ⋮ Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases ⋮ Some Graph-Colouring Theorems with Applications to Generalized Connection Networks

This page was built for publication: A fast parallel algorithm for routing in permutation networks