{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,20]],"date-time":"2025-04-20T04:43:23Z","timestamp":1745124203950},"reference-count":20,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4850,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1993,7]]},"abstract":"Abstract<\/jats:title>Circuit\u2010switched fixed routing (CSFR) is an increasingly popular communication model wherein there is between every source\u2014destination pair a single path that is system\u2010determined by a fixed\u2010routing rule. This paper studies the new problem of off\u2010line permutation scheduling on linear arrays, rings, hypercubes, and 2\u2010dimensional arrays, assuming the CSFR model. Optimal permutation scheduling involves finding a minimum number of subsets of nonconflicting source\u2014destination paths. Every subset of paths can be established to run in one pass. In this paper, optimal permutation scheduling on linear arrays is shown to be linear, and on rings, NP\u2010complete. On hypercubes, the problem is NP\u2010complete. However, we will give an O<\/jats:italic>(N<\/jats:italic> log N<\/jats:italic>) algorithm that routes any permutation in two passes if the model is relaxed to allow for two routing rules, namely, the so\u2010called e<\/jats:italic>\u2010cube rule and the e<\/jats:italic>\u22121<\/jats:sup>\u2010cube rule. This complexity is reduced to O(N)<\/jats:italic> hypercube\u2010parallel time. Finally, an O<\/jats:italic>(N<\/jats:italic> log2<\/jats:sup> N<\/jats:italic>) bipartite\u2010matching\u2010based algorithm will be designed to schedule any permutation on p<\/jats:italic> \u00d7 q<\/jats:italic> meshes\/tori in q<\/jats:italic> passes. \u00a9 1993 by John Wiley & Sons, Inc.<\/jats:italic><\/jats:p>","DOI":"10.1002\/net.3230230424","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T15:17:44Z","timestamp":1178983064000},"page":"441-448","source":"Crossref","is-referenced-by-count":2,"title":["Off\u2010line permutation routing on circuit\u2010switched fixed\u2010routing networks"],"prefix":"10.1002","volume":"23","author":[{"given":"Abdou","family":"Youssef","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Mathematical Theory on Connecting Networks and Telephone Traffic","author":"Benes V. E.","year":"1965"},{"key":"e_1_2_1_3_2","unstructured":"S. H.Bokhari Communication overheads on the Intel iPSC\u20102 hypercube. ICASE Interim Report 10 (May1990)."},{"key":"e_1_2_1_4_2","unstructured":"R.BoppanaandC. S.Raghavendra On self routing in Benes and shuffle exchange networks.Proc. Int'l Conf. Par. Proc.(Aug.1988)196\u2013200."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0601025"},{"key":"e_1_2_1_6_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/62.322423"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675260"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120410"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-59-02603-1"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224157"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676970"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.6312171"},{"key":"e_1_2_1_14_2","series-title":"Computer Science Series","volume-title":"Introduction to Combinatorial Mathematics","author":"Liu C. L.","year":"1968"},{"key":"e_1_2_1_15_2","series-title":"Technical Report GWU\u2010IIST\u201091\u201021","volume-title":"Simultaneous task migration on circuit\u2010switched hypercube multi\u2010processors","author":"Liu L.","year":"1991"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/322169.322172"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675791"},{"key":"e_1_2_1_18_2","volume-title":"Combinatorial Optimization, Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1982"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676812"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"e_1_2_1_21_2","unstructured":"A.Youssef Online communication on circuit\u2010switched fixed routing meshes.Proceedings of the Int'l Parallel Processing Symposium California (March1992)."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230230424","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230230424","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T03:37:50Z","timestamp":1698205070000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230230424"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["10.1002\/net.3230230424"],"URL":"https:\/\/doi.org\/10.1002\/net.3230230424","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,7]]}}}