[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

One-to-one disjoint path covers on k-ary n-cubes

Published: 01 August 2011 Publication History

Abstract

The k-ary n-cube, Q"n^k, is one of the most popular interconnection networks. Let n>=2 and k>=3. It is known that Q"n^k is a nonbipartite (resp. bipartite) graph when k is odd (resp. even). In this paper, we prove that there exist r vertex disjoint paths {P"i|0@?i@?r-1} between any two distinct vertices u and v of Q"n^k when k is odd, and there exist r vertex disjoint paths {R"i|0@?i@?r-1} between any pair of vertices w and b from different partite sets of Q"n^k when k is even, such that @?"i"="0^r^-^1P"i or @?"i"="0^r^-^1R"i covers all vertices of Q"n^k for 1@?r@?2n. In other words, we construct the one-to-one r-disjoint path cover of Q"n^k for any r with 1@?r@?2n. The result is optimal since any vertex in Q"n^k has exactly 2n neighbors.

References

[1]
E. Anderson, J. Brooks, C. Grassl, S. Scott, Performance of the Cray T3E Multiprocessor, in: Proceedings of the 1997 ACM/IEEE Conference on Supercomputing, SC-97, 1997, pp. 1-17.
[2]
Bondy, J.A. and Murty, U.S.R., Graph Theoery with Applications. 1980. North-Holland, New York.
[3]
S. Borkar, et al. iWarp: an integrated solution to high-speed parallel computing, in: Proceedings of the 1988 ACM/IEEE Conference on Supercomputing, SC-88, 1988, pp. 330-339.
[4]
Bose, B., Broeg, B., Kwon, Y. and Ashir, Y., Lee distance and topological properties of k-ary n-cubes. IEEE Transactions on Computers. v44. 1021-1030.
[5]
Chen, X.-B., Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs. Information Processing Letters. v110. 203-205.
[6]
Day, K. and Al-Ayyoub, A.E., Fault diameter of k-ary n-cube networks. IEEE Transactions on Parallel and Distributed Systems. v8. 903-907.
[7]
Fink, J., Perfect matchings extend to hamilton cycles in hypercubes. Journal of Combinatorial Theory, Series B. v97. 1074-1076.
[8]
Fu, J.-S., Chen, G.-H. and Duh, D.-R., Node-disjoint paths and related problems on hierarchical cubic networks. Networks. v40. 142-154.
[9]
Gomes, T., Craveirinha, J. and Jorge, L., An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs. Computers & Operations Research. v36. 1670-1682.
[10]
Harary, F., Hayes, J.P. and Wu, H.-J., A survey of the theory of the hypercube graphs. Computer Mathematics with Applications. v15. 277-289.
[11]
Hsieh, S.-H. and Lin, T.-L., Panconnectivity and edge-pancyclicity of k-ary n-cubes. Networks. v54. 1-11.
[12]
Hsieh, S.-H., Lin, T.-L. and Huang, H.-L., Panconnectivity and edge-pancyclicity of 3-ary n-cubes. The Journal of Supercomputing. v42. 225-233.
[13]
Hsu, H.-C., Lin, C.-K., Huang, H.-M. and Hsu, L.-H., The spanning connectivity of the (n,k)-star graphs. International Journal of Foundations of Computer Science. v17. 415-434.
[14]
Huang, C.-H., Strongly hamiltonian laceability of the even k-ary n-cube. Computers and Electrical Engineering. v35. 659-663.
[15]
Kao, S.-S., Hsu, K.-M. and Hsu, L.-H., Cubic planar hamiltonian graphs of various types. Discrete Mathematics. v306. 1364-1389.
[16]
Kao, S.-S., Hsu, H.-C. and Hsu, L.-H., Globally bi-3¿-connected graphs. Discrete Mathematics. v309. 1931-1946.
[17]
R.E. Kessler, J.L. Schwarzmeier, CRAY T3D: a new dimension for cray research, in: Proceedings of 38th Internationl Computer Conference, COMPCON-93, 1993, pp. 176-182.
[18]
Kobeissi, M. and Mollard, M., Disjoint cycles and spanning graphs of hypercubes. Discrete Mathematics. v288. 73-87.
[19]
Lin, C.-K., Huang, H.-M., Tan, Jimmy J.M. and Hsu, L.-H., On Spanning Connected Graphs. Discrete Mathematics. v308. 1330-1333.
[20]
Lin, C.-K., Tan, Jimmy J.M. and Hsu, L.-H., On the spanning connectively and spanning laceability of hypercube-like networks. Theoretical Computer Science. v381. 218-229.
[21]
Liu, C., Yarvis, M., Conner, W.S. and Guo, X., Guaranteed on-demand discovery of node-disjoint paths in Ad Hoc networks. Computer Communications. v30. 2917-2930.
[22]
M.D. Noakes, D.A. Wallach, W.J. Dally, The J-machine multicomputer: an architectural evaluation, in: Proceedings of the 20th Annual International Symposium on Computer Architecture, ISCA-93, 1993, pp. 224-235.
[23]
Ntafos, S.C. and Hakimi, S.L., On path cover problems in digraphs and applications to program testing. IEEE Transactions on Software Engineering. v5. 520-529.
[24]
Ore, O., Hamiltonian connected graphs. Journal de Mathématiques Pures et Appliquées. v42. 21-27.
[25]
Park, J.-H., Kim, H.-C. and Lim, H.-S., Many-to-many path covers in the presence of faulty elements. IEEE Transactions on Computers. v58. 528-540.
[26]
Stewart, I.A. and Xiang, Y., Bipanconnectivity and bipancyclicity in k-ary n-cubes. IEEE Transactions on Parallel and Distributed Systems. v20. 25-33.
[27]
Stewart, I.A. and Xiang, Y., Embedding long Paths in k-ary n-cubes with faulty nodes and links. IEEE Transactions on Parallel and Distributed Systems. v19. 1071-1085.
[28]
Sun, C.-M., Lin, C.-K., Huang, H.-M. and Hsu, L.-H., Mutually independent hamiltonian paths and cycles in hypercubes. Journal of Interconnection Networks. v7. 235-255.
[29]
Tsai, C.-H., Cycles embedding in hypercubes with node failures. Information Processing Letters. v102. 242-246.
[30]
Linear array and ring embeddings in conditional faulty hypercubes. Theoretical Computer Science. v314. 431-443.
[31]
D. Wang, T. An, M. Pan, K. Wang, S. Qu, Hamiltonian-like properies of k-ary n-cubes, in: Proceedings of Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT05, 2005, pp. 1002-1007.
[32]
Wu, R.-Y., Chen, G.-H., Kuo, Y.-L. and Chang, G.J., Node-disjoint paths in hierarchical hypercube networks. Information Sciences. v177. 4200-4207.
[33]
Yang, M.-C., Tan, Jimmy J.M. and Hsu, L.-H., Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes. Journal of Parallel and Distributed Computing. v67. 362-368.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science
Theoretical Computer Science  Volume 412, Issue 35
August, 2011
291 pages

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 August 2011

Author Tags

  1. Disjoint path cover
  2. Hamiltonian
  3. Hypercube
  4. k-ary n-cube

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 10 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media