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

DOI10.1016/S0020-0190(00)00022-3zbMATH Open1338.68015OpenAlexW1966252990MaRDI QIDQ294745FDOQ294745

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

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

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)

Cites Work

• Deadlock-Free Message Routing in Multiprocessor Interconnection Networks
• Deadlock-Free Packet Switching Networks
• Some Complexity Results in the Design of Deadlock-Free Packet Switching Networks
• Title not available (Why is that?)
• Efficient deadlock-free routing
• Requirements for deadlock-free, adaptive packet routing

Cited In (4)

• Deadlock prevention by acyclic orientations
• Title not available (Why is that?)
• Ranks of graphs: The size of acyclic orientation cover for deadlock-free packet routing
• 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)