Volume 18, Issue 2 (10-2023)
IJMSI 2023, 18(2): 185-198 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Rajan R S, Rajalaxmi T M, Stephen S, Shantrinal A A, Kumar K J. Embedding Wheel - like Networks. IJMSI 2023; 18 (2) :185-198
URL: http://ijmsi.ir/article-1-1601-en.html
URL: http://ijmsi.ir/article-1-1601-en.html
Abstract:
One of the important features of an interconnection network is its ability to efficiently simulate programs or parallel algorithms written for other architectures. Such a simulation problem can be mathematically formulated as a graph embedding problem. In this paper we compute the lower bound for dilation and congestion of embedding onto wheel-like networks. Further, we compute the exact dilation of embedding wheellike networks into hypertrees, proving that the lower bound obtained is sharp. Again, we compute the exact congestion of embedding windmill graphs into circulant graphs, proving that the lower bound obtained is sharp. Further, we compute the exact wirelength of embedding wheels and fans into 1,2-fault hamiltonian graphs. Using this we estimate the exact wirelength of embedding wheels and fans into circulant graphs, generalized Petersen graphs, augmented cubes, crossed cubes, Möbius cubes, twisted cubes, twisted n-cubes, locally twisted cubes, generalized twisted cubes, odd-dimensional cube connected cycle, hierarchical cubic networks, alternating group graphs, arrangement graphs, 3-regular planer hamiltonian graphs, star graphs, generalised matching networks, fully connected cubic networks, tori and 1-fault traceable graphs.
Type of Study: Research paper |
Subject:
General
References
1. J. Fan, X. Lin, X. Jia, Optimal Path Embedding in Crossed Cubes, IEEE Transactions on Parallel and Distributed Systems, 16(12), (2005), 1190-1200. [DOI:10.1109/TPDS.2005.151]
2. C. N. Kuo, Y. H. Cheng, Cycles Embedding in Folded Hypercubes with Conditionally Faulty Vertices, Discrete Applied Mathematics, 220, (2017), 55-59. [DOI:10.1016/j.dam.2016.12.008]
3. J. M. Xu, Topological Structure and Analysis of Interconnection Networks, Network theory and applications, Springer Science & Business Media, 7, 2013.
4. R. S. Rajan, T. M. Rajalaxmi, J. B. Liu, G. Sethuraman, Wirelength of Embedding Complete Multipartite Graphs into Certain Graphs, Discrete Applied Mathematics, 280, (2020), 221-236. [DOI:10.1016/j.dam.2018.05.034]
5. Y. L. Lai, K. Williams, A Survey of Solved Problems and Applications on Bandwidth, Edgesum, and Profile of Graphs, Journal of Graph Theory, 31, (1999), 75-94.
https://doi.org/10.1002/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S [DOI:10.1002/(SICI)1097-0118(199906)31:23.0.CO;2-S]
6. T. J. Lin, S. Y. Hsieh, J. S. T. Juan, Embedding Cycles and Paths in Product Networks and their Applications to Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, 23(6), (2012), 1081-1089. [DOI:10.1109/TPDS.2011.245]
7. M. Liu, H. Liu, Paths and Cycles Embedding on Faulty Enhanced Hypercube Networks, Acta Mathematica Scientia, 33(1), (2013), 227-246. [DOI:10.1016/S0252-9602(12)60207-0]
8. C. Chen, C. H. Tsai, L. H. Hsu, J. M. Tan, Pn Some Super Fault-tolerant Hamiltonian Graphs, Applied Mathematics and Computation, 148(3), (2004), 729-741. [DOI:10.1016/S0096-3003(02)00933-5]
9. M. R. Garey, D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
10. J. H. Park, H. S. Lim, H. C. Kim, Panconnectivity and Pancyclicity of Hypercube-like Interconnection Networks with Faulty Elements, Theoretical Computer Science, 377(1-3), (2007), 170-180. [DOI:10.1016/j.tcs.2007.02.029]
11. M. Arockiaraj, P. Manuel, I. Rajasingh, B. Rajan, Wirelength of 1-fault Hamiltonian Graphs into Wheels and Fans, Information Processing Letters, 111, (2011), 921-925. [DOI:10.1016/j.ipl.2011.06.011]
12. C. H. Tsai, T. K. Li, Two Construction Schemes for Cubic Hamiltonian 1-nodehamiltonian Graphs, Mathematical and Computer Modelling, 48(3-4), (2008), 656-661. [DOI:10.1016/j.mcm.2007.11.015]
13. S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Röttger, U. P. Schroeder, Embedding of Hypercubes into Grids, MFCS, (1998), 693-701. [DOI:10.1007/BFb0055820]
14. P. Manuel, I. Rajasingh, B. Rajan, H. Mercy, Exact Wirelength of Hypercube on a Grid, Discrete Applied Mathematics, 157(7), (2009), 1486-1495. [DOI:10.1016/j.dam.2008.09.013]
15. J. M. Xu, M. Ma, Survey on Path and Cycle Embedding in Some Networks, Frontiers of Mathematics in China, 4, (2009), 217-252. [DOI:10.1007/s11464-009-0017-5]
16. S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Röttger, U. P. Schroeder, The Congestion of n-cube Layout on a Rectangular Grid, Discrete Mathematics, 213, (2000), 13-19. [DOI:10.1016/S0012-365X(99)00162-4]
17. J. Opatrny, D. Sotteau, Embeddings of Complete Binary Trees into Grids and Extended Grids with Total Vertex-congestion 1, Discrete Applied Mathematics, 98, (2000), 237-254. [DOI:10.1016/S0166-218X(99)00161-4]
18. J. D. Chavez, R. Trapp, The Cyclic Cutwidth of Trees, Discrete Applied Mathematics, 87, (1998), 25-32. [DOI:10.1016/S0166-218X(98)00098-5]
19. I. Rajasingh, J. Quadras, P. Ma, A. William, Embedding of Cycles and Wheels into Arbitrary Trees, Networks, 44, (2004), 173-178. [DOI:10.1002/net.20027]
20. W. K. Chen, M. F. M. Stallmann, On Embedding Binary Trees into Hypercubes, Journal on Parallel and Distributed Computing, 24, (1995), 132 -138. [DOI:10.1006/jpdc.1995.1013]
21. P. Manuel, M. Arockiaraj, I. Rajasingh, B. Rajan, Embedding Hypercubes into Cylinders, Snakes and Caterpillars for Minimizing Wirelength, Discrete Applied Mathematics, 159(17), (2011), 2109-2116. [DOI:10.1016/j.dam.2011.07.003]
22. I. Rajasingh, B. Rajan, R. S. Rajan, Embedding of Special Classes of Circulant Networks, Hypercubes and Generalized Petersen Graphs, International Journal of Computer Mathematics, 89(15), (2012), 1970-1978. [DOI:10.1080/00207160.2012.697557]
23. J. Fan, X. Jia, Embedding Meshes into Crossed Cubes, Information Sciences, 177(15), (2007), 3151-3160. [DOI:10.1016/j.ins.2006.12.010]
24. Y. Han, J. Fan, S. Zhang, J. Yang, P. Qian, Embedding Meshes into Locally Twisted Cubes, Information Sciences, 180(19), (2010), 3794-3805. [DOI:10.1016/j.ins.2010.06.001]
25. X. Yang, Q. Dong, Y. Y. Tan, Embedding Meshes/tori in Faulty Crossed Cubes, Information Processing Letters, 110(14-15), (2010), 559-564. [DOI:10.1016/j.ipl.2010.04.007]
26. R. Caha, V. Koubek, Optimal Embeddings of Ladders into Hypercubes, Discrete Mathematics, 233, (2001), 65-83. [DOI:10.1016/S0012-365X(00)00227-2]
27. B. Chen, On Embedding Rectangular Grids in Hypercubes, IEEE Transactions on Computers, 37(10), (1988), 1285-1288. [DOI:10.1109/12.5991]
28. J. A. Ellis, Embedding Rectangular Grids into Square Grids, IEEE Transactions on Computers, 40(1), (1991), 46-52. [DOI:10.1109/12.67319]
29. M. Rottger, U. P. Schroeder, Efficient Embeddings of Grids into Grids, Discrete Applied Mathematics, 108(1-2), (2001), 143-173. [DOI:10.1016/S0166-218X(00)00224-9]
30. C. -H. Tsai, Embedding of Meshes in Möbius Cubes, Theoretical Computer Science, 401(1-3), (2008), 181-190. [DOI:10.1016/j.tcs.2008.04.023]
31. P. -L. Lai, C. -H. Tsai, Embedding of Tori and Grids into Twisted Cubes, Theoretical Computer Science, 411(40-42), (2010), 3763-3773. [DOI:10.1016/j.tcs.2010.06.029]
32. I. Rajasingh, M. Arockiaraj, B. Rajan, P. Manuel, Minimum Wirelength of Hypercubes into n-dimensional Grid Networks, Information Processing Letters, 112, (2012), 583-586. [DOI:10.1016/j.ipl.2012.04.008]
33. I. Rajasingh, B. Rajan, R. S. Rajan, Embedding of Hypercubes into Necklace, Windmill and Snake Graphs, Information Processing Letters, 112, (2012), 509-515. [DOI:10.1016/j.ipl.2012.03.006]
34. I. Rajasingh, P. Manuel, B. Rajan, M. Arockiaraj, Wirelength of Hypercubes into Certain Trees, Discrete Applied Mathematics, 160, (2012), 2778 - 2786. [DOI:10.1016/j.dam.2011.12.007]
35. B. R. Myers, Number of Spanning Trees in a Wheel, IEEE Transactions on Circuit Theory, 18, (1971), 280-282. [DOI:10.1109/TCT.1971.1083273]
36. Slamin, M. Bača, Y. Lin, M. Miller, R. Simanjuntak, Edge-magic Total Labelings of Wheels, Fans and Friendship Graphs, Bulletin of the Institute of Combinatorics and its Applications, 35, (2002), 89-98.
37. J. R. Goodman, C. H. Sequin, A Multiprocessor Interconnection Topology, IEEE Transactions on Computers, c-30(12), (1981), 923-933. [DOI:10.1109/TC.1981.1675731]
38. J. C. Bermond, F. Comellas, D. F. Hsu, Distributed Loop Computer Networks, A survey: Journal of Parallel and Distributed Computing, 24(1), (1995), 2-10. [DOI:10.1006/jpdc.1995.1002]
39. T. C. Mai, J. J. Wang, L. -H. Hsu, Hyperhamiltonian Generalized Petersen Graphs, Computer and Mathematics with Applications, 55(9), (2008), 2076-2085. [DOI:10.1016/j.camwa.2007.08.041]
40. S. A. Choudum and V. Sunitha, Augmented Cubes, Networks, 40(2), (2002), 71-84. [DOI:10.1002/net.10033]
41. E. Efe, A Variation on the Hypercube with Lower Diameter, IEEE Transactions on Computers, 40(11), (1991), 1312-1316. [DOI:10.1109/12.102840]
42. P. Cull, S. M. Larson, The M¨obius Cubes, IEEE Transactions on Computers, 44(5), (1995), 647-659. [DOI:10.1109/12.381950]
43. J. Fan, X. Jia, X. Lin, Optimal Embeddings of Paths with Various Lengths in Twisted Cubes, IEEE Transactions on Parallel and Distributed Systems, 18(4), (2007), 511-521. [DOI:10.1109/TPDS.2007.1003]
44. J. Fan, X. Jia, X. Lin, Embedding of Cycles in Twisted Cubes with Edge Pancyclic, Algorithmica, 51(3), (2008), 264-282. [DOI:10.1007/s00453-007-9024-7]
45. J. -H. Park, H. -C. Kim, H. -S. Lim, Fault-hamiltonicity of Hypercube-like Interconnection Networks, in: Proc. of IEEE International Parallel and Distributed Processing Symposium, IPDPS 2005, Denver, 2005.
46. X. Yang, G. M. Megson, D. J. Evans, Locally Twisted Cubes are 4-pancyclic, Applied Mathematics Letters, 17, (2004), 919-925. [DOI:10.1016/j.aml.2003.10.009]
47. K. Ghose, K. R. Desai, Hierarchical Cubic Networks, IEEE Transactions on Parallel and Distribted Systems, 6(4), (1995), 427-435. [DOI:10.1109/71.372797]
48. J. -M. Chang, J. -S. Yang, Y. -L. Wang, Y. Cheng, Panconnectivity, Fault Tolerant Hamiltonicity and Hamiltonian-connectivity in Alternating Group Graphs, Networks, 44, (2004), 302-310. [DOI:10.1002/net.20039]
49. K. Day, A. Tripathi, Arrangement Graphs: A Class of Generalized Star Graphs, Information Processing Letters, 42(5), (1992), 235-241. [DOI:10.1016/0020-0190(92)90030-Y]
50. J. J. Wang, C. N. Hung, L. H. Hsu, Optimal 1-hamiltonian Graphs, Information Processing Letters, 65(3), (1998), 157-161. [DOI:10.1016/S0020-0190(98)00004-0]
51. H. C. Hsu, Y. L. Hsieh, J. J. M. Tan, L.-H. Hsu, Fault Hamiltonicity and Fault Hamiltonian Connectivity of the (n; k)-star Graphs, Networks, 42(4), (2003), 189-201. [DOI:10.1002/net.10096]
52. Q. Donga, X. Yanga, J. Zhaob, Fault Hamiltonicity and Fault Hamiltonian-connectivity of Generalised Matching Networks, International Journal of Parallel, Emergent and Distributed Systems, 24(5), (2009), 455-461. [DOI:10.1080/17445760902774070]
53. T. Y. Ho, C. K. Lin, Fault-tolerant Hamiltonian Connectivity and Fault-tolerant Hamiltonicity of the Fully Connected Cubic Networks, Journal of Information Science and Engineering, 25, (2009), 1855-1862.
54. H. C. Kim, J. H. Park, Fault Hamiltonicity of Two-dimensional Torus Networks, in: Proc. Japan-Korea Joint Workshop on Algorithms and Computation, (2000), 110-117.
55. H. -C. Kim, J. -H. Park, Paths and Cycles in d-dimensional Tori with Faults, in: Workshop on Algorithms and Computation WAAC01, Pusan, Korea, (2001), 67-74.
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
