{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T06:12:34Z","timestamp":1781590354787,"version":"3.54.5"},"reference-count":15,"publisher":"Wiley","issue":"7","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5793,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1990,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the problem of predicting whether a deadlock will necessarily occur in a store\u2010and\u2010forward network. We define two versions of this problem, depending on whether or not the routes to be followed by packets are fixed. For networks with only one buffer per vertex, both versions of this problem are shown to be NP\u2010complete even for simple classes of graphs (among others bipartite graphs, two terminal series\u2010parallel [TTSP] graphs and therefore planar graphs). On the other hand, the same problems are shown to be polynomially solvable for treelike networks. In this case, two efficient algorithms for checking whether a treelike network with <jats:italic>n<\/jats:italic> vertices and <jats:italic>p<\/jats:italic> packets is bound to deadlock are proposed. The former has an <jats:italic>O(pn)<\/jats:italic> time and space complexity, whereas the latter runs in <jats:italic>O(n<\/jats:italic> log <jats:italic>n<\/jats:italic>)<jats:sup>1<\/jats:sup> time and requires <jats:italic>O(n)<\/jats:italic> space. In the case of multibuffered networks, both versions of the problem are shown to be NP\u2010complete even on treelike networks.<\/jats:p>","DOI":"10.1002\/net.3230200705","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T10:18:20Z","timestamp":1178965100000},"page":"861-881","source":"Crossref","is-referenced-by-count":13,"title":["Predicting deadlock in store\u2010and\u2010forward networks"],"prefix":"10.1002","volume":"20","author":[{"given":"Claudio","family":"Arbib","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gluseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Panconesl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"J.Blazewicz D. P.Bovet andG.Gambosi Deadlock\u2010resistant flow control procedures for store\u2010and\u2010forward networks.IEEE Trans. Commun. COM\u201032(1984)884\u2013887.","DOI":"10.1109\/TCOM.1984.1096151"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"J.Blazewicz J.Brzezinski andG.Gambosi Time\u2010stamps approach to store\u2010and\u2010forward deadlock prevention.IEEE\u2010Trans. Comm. COM\u201035(1987)490\u2013495.","DOI":"10.1109\/TCOM.1987.1096799"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170205"},{"key":"e_1_2_1_6_2","article-title":"Detection and removal of deadlocks in store\u2010and\u2010forward communications networks","volume":"84","author":"Bovet D. P.","journal-title":"Performance"},{"key":"e_1_2_1_7_2","unstructured":"G.Campanile II problema dello stallo in reti store\u2010and\u2010forward Tesi di laurea in matematica Dipartimento di Matematica Universith di Roma \u201cLa Sapienza \u201d Rome Italy (in Italian) (1984)."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/356603.356607"},{"key":"e_1_2_1_9_2","volume-title":"Queueing Systems, Vol. II: Computer applications","author":"Kleinrock L.","year":"1976"},{"key":"e_1_2_1_10_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"P. M.MerlinandP. J.Schweitzer Deadlock avoidance in store\u2010and\u2010forward networks I: Store\u2010and\u2010forward deadlock.IEEE Trans. Comm. COM\u201028(1980)345\u2013354.","DOI":"10.1109\/TCOM.1980.1094666"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"P. M.MerlinandP. J.Schweitzer Deadlock avoidance in store\u2010and\u2010forward networks II: Other deadlock types.IEEE Trans. Comm. COM\u201028(1980)355\u2013360.","DOI":"10.1109\/TCOM.1980.1094667"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"S.Toueg Deadlock\u2010 and livelock\u2010 free packet switching networks.Proc. ACM Symp. Theory Comput.(1980)94\u2013108.","DOI":"10.1145\/800141.804656"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210053"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"S.TouegandJ. D.Ullman Deadlock\u2010free packet switching networks.Proc. ACM Symp. Theory Comput.(1979)89\u201398.","DOI":"10.1145\/800135.804402"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230200705","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230200705","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T19:34:17Z","timestamp":1698003257000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230200705"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,12]]},"references-count":15,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1990,12]]}},"alternative-id":["10.1002\/net.3230200705"],"URL":"https:\/\/doi.org\/10.1002\/net.3230200705","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,12]]}}}