Acyclic orientations do not lead to optimal deadlock-free packet routing algorithms

DOI10.1016/S0020-0190(00)00022-3MaRDI QIDQ294745zbMATHOpenAlexFDO

Authors D. Štefankovič

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019000000223?np=y

zbMATH Keywords

interconnection networksacyclic orientationsdeadlock-free packet routing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Network design and communication in computer systems (68M10)

Recommendations

• scientific article; zbMATH DE number 1107721
• Optimal centralized algorithms for store-and-forward deadlock avoidance
• Deadlock prevention by acyclic orientations
• Deadlock-Free Message Routing in Multiprocessor Interconnection Networks
• Requirements for Deadlock-Free, Adaptive Packet Routing

Cites work

• scientific article; zbMATH DE number 732976 (Why is no real title available?)
• Deadlock-Free Message Routing in Multiprocessor Interconnection Networks
• Deadlock-Free Packet Switching Networks
• Efficient deadlock-free routing
• Requirements for deadlock-free, adaptive packet routing
• Some Complexity Results in the Design of Deadlock-Free Packet Switching Networks

Cited in

(4)

• Deadlock prevention by acyclic orientations
• Ranks of graphs: The size of acyclic orientation cover for deadlock-free packet routing
• scientific article; zbMATH DE number 1107721 (Why is no real title available?)
• On the flattest common supersequence method for deadlock-free routing in arbitrary networks

This page was built for publication: Acyclic orientations do not lead to optimal deadlock-free packet routing algorithms

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