{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T13:40:34Z","timestamp":1748785234910},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1990,9]]},"abstract":"<jats:p> One of the main issues in flow control problems is deadlock of messages caused by a limited amount of resources. In this paper, the problem of predicting whether a deadlock will necessarily occur in a Store-and-Forward Network is analyzed. We show that, in the case of dynamic routing, the deadlock prediction problem can be decided in polynomial time if tokens are allowed to transit more than once through the same vertex, in contrast with an NP-completeness result in the case where they are allowed to transit at most once. <\/jats:p>","DOI":"10.1142\/s012905419000014x","type":"journal-article","created":{"date-parts":[[2004,11,29]],"date-time":"2004-11-29T02:14:37Z","timestamp":1101694477000},"page":"185-199","source":"Crossref","is-referenced-by-count":3,"title":["DEADLOCK PREDICTION IN THE CASE OF DYNAMIC ROUTING"],"prefix":"10.1142","volume":"01","author":[{"given":"DANIEL P.","family":"BOVET","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, 00185 Roma, Italy"}]},{"given":"MIRIAM","family":"DI IANNI","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, 00185 Roma, Italy"}]},{"given":"PIERLUIGI","family":"CRESCENZI","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica, Universit\u00e0 de L\u2019Aquila, 67010 L\u2019Aquila, Italy"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905419000014X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T14:07:27Z","timestamp":1565186847000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905419000014X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[1990,9]]}},"alternative-id":["10.1142\/S012905419000014X"],"URL":"https:\/\/doi.org\/10.1142\/s012905419000014x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,9]]}}}