Some Complexity Results in the Design of Deadlock-Free Packet Switching Networks
Sam Toueg, Kenneth Steiglitz · SIAM Journal on Computing · 1981
Deadlocks are very serious system failures and have been observed in existing packet switching networks (PSN’s). Several problems related to the design of deadlock-free PSN’s are investigated here. Polynomial-time algorithms are given for some of these problems, but most of them are shown to be NP-complete or NP-hard, and therefore polynomial-time algorithms are not likely to be found.