{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T13:40:09Z","timestamp":1648647609757},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J CIRCUIT SYST COMP"],"published-print":{"date-parts":[[1992,6]]},"abstract":"<jats:p> Single Row Routing problem is one of the important subproblems in the layout design of multilayer printed circuit boards. This routing technique has also been applied to routing of microwave citcuits and other routing problems. The single row routing problem has been extensively studied and several sequential algorithms have been proposed. <\/jats:p><jats:p> In this paper, we present a parallel hypercube algorithm for the single row routing problem. The basis of this parallel algorithm is a new O(n<jats:sup>2<\/jats:sup> log n) sequential algorithm based on the concept of modified cut numbers and a graph decomposition scheme. The sequential algorithm is based on generalizing the concepts underlying two existing sequential algorithms. A parallel algorithm for the hypercube architecture with N processors is then developed by combining the nice features of the sequential algorithm with an efficient allocation scheme. This results in a parallel algorithm of [Formula: see text] complexity. The experimental results show that our algorithm achieves a speed up factor that is quite close to the theoretical bound while maintaining the quality of the solutions, as compared to any existing sequential algorithm. Moreover, the algorithm produces 28% better results than any existing results. <\/jats:p>","DOI":"10.1142\/s0218126692000106","type":"journal-article","created":{"date-parts":[[2004,11,24]],"date-time":"2004-11-24T19:50:24Z","timestamp":1101325824000},"page":"113-139","source":"Crossref","is-referenced-by-count":0,"title":["A PARALLEL ALGORITHM FOR SINGLE ROW ROUTING PROBLEMS"],"prefix":"10.1142","volume":"02","author":[{"given":"ARNOB","family":"ROY","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Nebraska-Lincoln, Lincoln, NE 68588\u20130115, USA"}]},{"given":"JITENDER","family":"DEOGUN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Nebraska-Lincoln, Lincoln, NE 68588\u20130115, USA"}]},{"given":"NAVEED A.","family":"SHERWANI","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Western Michigan University, Kalamazoo, MI 49008, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["Journal of Circuits, Systems and Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218126692000106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:44:32Z","timestamp":1565131472000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218126692000106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1992,6]]}},"alternative-id":["10.1142\/S0218126692000106"],"URL":"https:\/\/doi.org\/10.1142\/s0218126692000106","relation":{},"ISSN":["0218-1266","1793-6454"],"issn-type":[{"value":"0218-1266","type":"print"},{"value":"1793-6454","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}