Optimality of a Two-Phase Strategy for Routing in Interconnection Networks

DOI10.1109/TC.1983.1676335MaRDI QIDQ3682403zbMATH OpenFDO

Authors Leslie G. Valiant

Publication date 1983

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

Full work available at URL https://doi.org/10.1109/TC.1983.1676335

zbMATH Keywords

d-way shuffle graphspacket switching networksparallel computationparallel computershuffle-exchange graph

Mathematics Subject Classification ID

Theory of operating systems (68N25) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Optimal routing algorithms for mesh-connected processor arrays
• scientific article; zbMATH DE number 4049037
• Packet routing and PRAM emulation on star graphs and leveled networks
• scientific article; zbMATH DE number 1173684
• Deterministic Permutation Routing on Meshes

Cited in

(21)

• Some results on subclass containment problems for special classes of dpda's related to nonsingular machines
• Superdeterministic DPDAs: The method of accepting does affect decision problems
• A representation of trees by languages. II
• Achievable high scores of \(\varepsilon\)-moves and running times in DPDA computations
• The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine
• On the decidability of equivalence for deterministic pushdown transducers
• DPDA's in 'Atomic normal form' and applications to equivalence problems
• Deterministic one-counter automata
• A result on the equivalence problem for deterministic pushdown automata
• The inclusion problem for simple languages
• A direct algorithm for checking equivalence of LL(k) grammars
• Economy of description by parsers, DPDA's, and PDA's
• A representation of trees by languages. I
• On equivalence and subclass containment problems for deterministic context-free languages
• A note on non-singular deterministic pushdown automata
• A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
• A new routing algorithm for the shuffle-exchange permutation network
• Towards a better understanding of pure packet routing
• On some decision questions concerning pushdown machines
• New families of non real time dpda's and their decidability results
• An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

This page was built for publication: Optimality of a Two-Phase Strategy for Routing in Interconnection Networks

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