{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T05:40:47Z","timestamp":1698298847016},"reference-count":16,"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":"<jats:title>Abstract<\/jats:title><jats:p>We study off\u2010line routing of permutations \u03c0 in arbitrary connected graphs. By insisting that routings be congestion\u2010free, we can rephrase the problem as one of factoring \u03c0 into a minimal length product of permutations that move messages a distance of at most one, or alternatively, as the problem of finding a shortest path from the identity permutation to \u03c0 in a certain Cayley graph of the symmetric group on the nodes. For the complete <jats:italic>k<\/jats:italic>\u2010partite graph <jats:italic>K<\/jats:italic><jats:sub><jats:italic>n,n<\/jats:italic>,\u2026.,<jats:italic>n<\/jats:italic><\/jats:sub>, every \u03c0 can be routed in two steps. We investigate a method for finding minimal factorizations. It involves finding perfect matchings in certain bipartite graphs associated with \u03c0. For the <jats:italic>n<\/jats:italic>\u2010dimensional hypercube <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, the well\u2010known upper bound of 2<jats:italic>n<\/jats:italic> \u2212 1 for the number of steps in which all \u03c0\u2032s can be routed (obtained via the Bene\u0161 network) is reduced to 2<jats:italic>n<\/jats:italic> \u2212 2. We prove some results about permutations of <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> that are close to the antipodal map. A number of examples on <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>3<\/jats:italic><\/jats:sub> and <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>4<\/jats:italic><\/jats:sub> illustrate our method and compare it with those used by others. \u00a9 <jats:italic>1993 by John Wiley &amp; Sons, Inc.<\/jats:italic><\/jats:p>","DOI":"10.1002\/net.3230230420","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T15:18:05Z","timestamp":1178983085000},"page":"391-398","source":"Crossref","is-referenced-by-count":14,"title":["Routing permutations on a graph"],"prefix":"10.1002","volume":"23","author":[{"given":"Mark","family":"Ramras","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090401"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0219037"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"J. A.BondyandU. S. R.Murty Graph Theory with Applications.North\u2010Holland New York (1976).","DOI":"10.1007\/978-1-349-03521-2"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210303"},{"key":"e_1_2_1_6_2","unstructured":"G.Cooperman private communication."},{"key":"e_1_2_1_7_2","unstructured":"G.CoopermanandL.Finkelstein New methods for using Cayley graphs in interconnection networks Disc. Appl. Math.(Special issue on interconnection networks) to appear."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90143-1"},{"key":"e_1_2_1_9_2","unstructured":"R. N.Draper A fast distributed routing algorithm for supertoroidal networks. Supercomputing Research Center Technical Report SRC\u2010TR\u201091\u2010032."},{"key":"e_1_2_1_10_2","first-page":"119","article-title":"An effective approach to fast data permutations in hypercube multiprocessors","volume":"84","author":"Latifi S.","year":"1991","journal-title":"Congress. Numerantium"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"F. T.Leighton Introduction to Parallel Algorithms and Architectures: Arrays \u00b7 Trees \u00b7 Hypercubes Morgan Kaufmann San Mateo CA (1992).","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675791"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/62044.62050"},{"key":"e_1_2_1_14_2","article-title":"Processor interconnection networks from Cayley graphs","author":"Schibell S. T.","journal-title":"Discrete Appl. Math."},{"key":"e_1_2_1_15_2","unstructured":"A. P.SpragueandH.Tamaki Routings for involutions of a hypercube. Preprint."},{"key":"e_1_2_1_16_2","unstructured":"T.Szymanski On the permutation capability of a circuit\u2010switched hypercube.International Conference on Parallel Processing I\u2010103\u2013I\u2010110 (1989)."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230230420","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230230420","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T03:37:40Z","timestamp":1698205060000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230230420"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["10.1002\/net.3230230420"],"URL":"https:\/\/doi.org\/10.1002\/net.3230230420","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]]}}}