Some Complexity Results in the Design of Deadlock-Free Packet Switching Networks

DOI10.1137/0210053MaRDI QIDQ3922167zbMATH OpenOpenAlexFDO

Authors Sam Toueg, Ken Steiglitz

Publication date 1981

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0210053

zbMATH Keywords

communication networkcomputer networkflow controlNP-completerouting

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Applications of graph theory to circuits and networks (94C15)

Cited in

(3)

• Acyclic orientations do not lead to optimal deadlock-free packet routing algorithms
• How to improve snap-stabilizing point-to-point communication space complexity?
• Avoiding deadlocks via weak deadlock sets

This page was built for publication: Some Complexity Results in the Design of Deadlock-Free Packet Switching Networks

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