{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T19:37:43Z","timestamp":1648928263017},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1991,9]]},"abstract":"<jats:p> In this paper, we propose a parallel algorithm for the traffic control problem (an NP-complete problem) on crossbar switch networks. This problem is to find a set of conflict-free paths such that the maximum number of message packets can be transmitted over the network. The problem can be represented by an energy function. Then by applying our parallel algorithm, the state of the energy function is iteratively updated toward a stable state. When the energy function reaches a stable state, the state represents a solution of the problem. The empirical results show that the throughputs of the proposed algorithm are much better than the linear algorithm. We have shown that the time complexity of a parallel algorithm is O(n) by using n<jats:sup>2<\/jats:sup> processors. Furthermore, since the traffic control problem can be reduced to the traveling salesman problem, the proposed algorithm can be further applied to some other NP-complete problems. <\/jats:p>","DOI":"10.1142\/s0129626491000215","type":"journal-article","created":{"date-parts":[[2004,11,25]],"date-time":"2004-11-25T12:12:21Z","timestamp":1101384741000},"page":"51-58","source":"Crossref","is-referenced-by-count":4,"title":["AN <font>O(n)<\/font> PARALLEL ALGORITHM FOR SOLVING THE TRAFFIC CONTROL PROBLEM ON CROSSBAR SWITCH NETWORKS"],"prefix":"10.1142","volume":"01","author":[{"given":"K. T.","family":"SUN","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chiao-Tung University, Hsin Chu, Taiwan 300, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H. C.","family":"FU","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chiao-Tung University, Hsin Chu, Taiwan 300, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626491000215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:58:46Z","timestamp":1565143126000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626491000215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[1991,9]]}},"alternative-id":["10.1142\/S0129626491000215"],"URL":"https:\/\/doi.org\/10.1142\/s0129626491000215","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}