Routing Permutations on Graphs via Factors |
| |
| Authors: | Dominique Barth Petri?or Panaite |
| |
| Affiliation: | 2. WeMind Institute, Miami Children’s Hospital, Miami, FL;1. Department of Psychiatry, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599, United States;2. Neurobiology Curriculum, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599, United States;3. Department of Cell Biology and Physiology, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599, United States;4. Department of Biomedical Engineering, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599, United States;5. Neuroscience Center, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599, United States;1. Computing Infrastructure Research Centre, McMaster University, Hamilton, Ontario, Canada;2. Department of Mechanical Engineering, McMaster University, Hamilton, Ontario, Canada;3. Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada;1. Institute of Biochemistry and Molecular Biology, School of Life Sciences, Lanzhou University, 222 Tianshui South Road, Lanzhou, 730000, China;2. Key Laboratory of Preclinical Study for New Drugs of Gansu Province, Lanzhou University, 222 Tianshui South Road, Lanzhou, 730000, China |
| |
| Abstract: | We deal with the permutation routing problem on graphs modeling interconnection networks. In our model, calledrouting via factors, at each routing step, the communication pattern is a directed 1-factor in a symmetric digraph. This adds a new feature, that of continuous packet movement, to preciously studied routing types, where the routing of a permutation is reduced to a sequence of permutations from a given class. We especially focus on bipartite graphs and we give sufficient conditions for a graph to be rearrangeable in our model. We propose a general technic for routing via factors that we apply to the 2D mesh and the hypercube. |
| |
| Keywords: | permutation routing factors bipartite graphs mesh hypercube |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
