A fast parallel algorithm for routing in permutation networks
From MaRDI portal
Publication:3904540
DOI10.1109/TC.1981.6312171zbMath0455.94047MaRDI QIDQ3904540
Nicholas J. Pippenger, Leslie G. Valiant, G. Lev
Publication date: 1981
Published in: IEEE Transactions on Computers (Search for Journal in Brave)
68M10: Network design and communication in computer systems
90B15: Stochastic network models in operations research
90B10: Deterministic network models in operations research
94C15: Applications of graph theory to circuits and networks
Related Items
Parallel algorithms for routing in nonblocking networks, Applications of matching and edge‐coloring algorithms to routing in clos networks, Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases, Multicommodity flows in simple multistage networks, Asymmetrical multiconnection three‐stage clos networks, Off‐line permutation routing on circuit‐switched fixed‐routing networks, Parallel random access machines with bounded memory wordsize, A parallel-design distributed-implementation (PDDI) general-purpose computer, Improved edge-coloring with three colors, Optimally edge-colouring outerplanar graphs is in NC, Counterexample to a conjecture of Szymanski on hypercube routing, A complexity theory of efficient parallel algorithms, On permutations of wires and states, Routing, merging, and sorting on parallel models of computation, Parallel O(log n) time edge-colouring of trees and Halin graphs, Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs, Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem, A parallel algorithm for approximating the minimum cycle cover, Approximating matchings in parallel, Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings, Restricted CRCW PRAMs, The probabilistic method yields deterministic parallel algorithms, The local nature of \(\Delta\)-coloring and its algorithmic applications, The generalized folding-cube network, Some Graph-Colouring Theorems with Applications to Generalized Connection Networks
