×

Many-to-many disjoint path covers in \(k\)-ary \(n\)-cubes. (English) Zbl 1277.68040

Summary: The class of \(k\)-ary \(n\)-cubes represents the most commonly used interconnection topology for parallel and distributed computing systems. Embedding of disjoint paths has attracted much attention in the parallel processing. In disjoint path problems, the many-to-many disjoint path problem is the most generalized one. This paper considers the problem of many-to-many disjoint path covers in the \(k\)-ary \(n\)-cube \(Q_n^k\) with even \(k\geq 4\), and obtains the following result. Let \(m\) be an integer with \(1\leq m\leq 2n-1\). For any two sets \(S\) and \(T\) of \(m\) vertices in different partite sets, \(Q_n^k\) has \(m\) disjoint \((S,T)\)-paths containing all vertices of \(Q_n^k\) and our result is optimal.

MSC:

68M14 Distributed systems
68M07 Mathematical problems of computer architecture
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI

References:

[1] Bose, Bella; Broeg, Bob; Kwon, Younggeun; Ashir, Yaagoub, Lee distance and topological properties of \(k\)-ary \(n\)-cubes, IEEE Transactions on Computers, 44, 8, 1021-1030 (1995) · Zbl 1054.68510
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory (2007), Springer: Springer New York · Zbl 1134.05001
[3] Chen, Xie-Bin, Many-to-many disjoint paths in faulty hypercubes, Information Sciences, 179, 18, 3110-3115 (2009) · Zbl 1193.68050
[4] Day, Khaled; Al-Ayyoub, Abdel-Elah, Fault diameter of \(k\)-ary \(n\)-cube networks, IEEE Transactions on Parallel and Distributed Systems, 8, 9, 903-907 (1997)
[5] Dvořák, Tomáš; Gregor, Petr, Partitions of faulty hypercubes into paths with prescribed endvertices, SIAM Journal on Discrete Mathematics, 22, 4, 1448-1461 (2008) · Zbl 1187.05056
[7] Lai, Pao-Lien; Hsu, Hong-Chun, The two-equal-disjoint path cover problem of Matching Composition Network, Information Processing Letters, 107, 1, 18-23 (2008) · Zbl 1186.68025
[8] Liu, Di; Li, Jing, Many-to-many \(n\)-disjoint path covers in \(n\)-dimensional hypercubes, Information Processing Letters, 110, 14-15, 580-584 (2010) · Zbl 1234.68020
[9] Park, Jung-Heum, Unpaired many-to-many disjoint path covers in hypercube-like interconnection networks, Journal of KISS, 33, 10, 789-796 (2006)
[10] Park, Jung-Heum; Kim, Hee-Chul; Lim, Hyeong-Seok, Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements, IEEE Transactions on Parallel and Distributed Systems, 17, 3, 227-240 (2006)
[11] Park, Jung-Heum; Kim, Hee-Chul; Lim, Hyeong-Seok, Many-to-many disjoint path covers in presence of faulty elements, IEEE Transactions on Computers, 58, 4, 528-540 (2009) · Zbl 1368.68090
[12] Shih, Yuan-Kang; Kao, Shin-Shin, One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes, Theoretical Computer Science, 412, 35, 4513-4530 (2011) · Zbl 1223.68086
[13] Stewart, Iain A.; Xiang, Yonghong, Embedding long paths in \(k\)-ary \(n\)-cubes with faulty nodes and links, IEEE Transactions on Parallel and Distributed Systems, 19, 8, 1071-1085 (2008)
[14] Wang, Shiying; Zhang, Shurong, Embedding hamiltonian paths in \(k\)-ary \(n\)-cubes with conditional edge faults, Theoretical Computer Science, 412, 46, 6570-6584 (2011) · Zbl 1228.68013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.