Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees

• Autorzy: Rajeshwari S. , Rajesh M.

Identyfikatory

DOI

10.3233/FI-222149

• Języki publikacji: EN

Abstrakty

EN

Graph embeddings play a significant role in the design and analysis of parallel algorithms. It is a mapping of the topological structure of a guest graph G into a host graph H, which is represented as a one-to-one mapping from the vertex set of the guest graph to the vertex set of the host graph. In multiprocessing systems, the interconnection networks enhance the efficient communication between the components in the system. Obtaining minimum wirelength in embedding problems is significant in the designing of networks and simulating one architecture by another. In this paper, we determine the wirelength of embedding 3-ary n-cubes into cylinders and certain trees.

Słowa kluczowe

EN

embedding; edge isoperimetric problem; congestion, wirelength; 3-ary n-cube

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 188, nr 4
• Strony: 269--284
• Opis fizyczny: Bibliogr. 82 poz., rys.

Twórcy

autor

Rajeshwari S.

• School of Advanced Sciences Vellore Institute of Technology Chennai-600127, India

autor

Rajesh M.

• School of Computer Science and Engineering Vellore Institute of Technology Chennai-600127, India

Bibliografia

• [1] Rajasingh I, William A, Quadras J, Manuel P. Embedding of cycles and wheels into arbitrary trees.
• Networks: An International Journal, 2004. 44(3):173–178.
• [2] Guu CJ. The circular wirelength problem for hypercubes. University of California, Riverside, 1997.
• [3] Yang M. Path embedding in star graphs. Appl. Math. Comput., 2009. 207(2):283–291.
• [4] Bezrukov SL. Embedding complete trees into the hypercube. Discret. Appl. Math., 2001. 110(2-
• 3):101–119. doi:10.1016/S0166-218X(00)00256-0.
• [5] Manuel PD, Arockiaraj M, Rajasingh I, Rajan B. Embedding hypercubes into cylinders, snakes and
• caterpillars for minimizing wirelength. Discret. Appl. Math., 2011. 159(17):2109–2116.
• doi:10.1016/j.dam.2011.07.003.
• [6] Feder T, Motwani R. Clique partitions, graph compression and speeding-up algorithms. Journal of
• Computer and System Sciences, 1995. 51(2):261–272. doi:10.1006/jcss.1995.1065.
• [7] Jungnickel D. Graphs, networks and algorithms. Springer, 2005. doi:10.1007/b138283.
• [8] White S, Smyth P. A spectral clustering approach to finding communities in graphs. In:
• Proceedings of the 2005 SIAM international conference on data mining. SIAM, 2005 pp. 274–285.
• [9] Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the
• American society for information science and technology, 2007. 58(7):1019–1031.
• doi:10.1002/asi.20591.
• [10] Bhagat S, Cormode G, Muthukrishnan S. Node classification in social networks. In: Social network
• data analytics, pp. 115–148. Springer, 2011. doi:10.1007/978-1-4419-8462-3 5.
• [11] Xu J. Topological structure and analysis of interconnection networks, volume 7. Springer Science
• & Business Media, 2013.
• [12] Bjerregaard T, Mahadevan S. A survey of research and practices of network-on-chip. ACM
• Computing Surveys (CSUR), 2006. 38(1):1–es. doi:10.1145/1132952.1132953.
• [13] Xiang D, Chakrabarty K, Fujiwara H. Multicast-based testing and thermal-aware test scheduling
• for 3D ICs with a stacked network-on-chip. IEEE Transactions on Computers, 2015. 65(9):2767–2779.
• doi:10.1109/TC.2015.2493548.
• [14] Benini L, De Micheli G. Networks on chips: A new SoC paradigm. computer, 2002. 35(1):70–78.
• doi:10.1109/2.976921.
• [15] Chittamuru SVR, Dang D, Pasricha S, Mahapatra R. BiGNoC: Accelerating big data computing with
• application-specific photonic network-on-chip architectures. IEEE Transactions on Parallel and
• Distributed Systems, 2018. 29(11):2402–2415. doi:10.1109/TPDS.2018.2833876.
• [16] Gu H, Chen K, Yang Y, Chen Z, Zhang B. MRONoC: A low latency and energy efficient on chip
• optical interconnect architecture. IEEE Photonics Journal, 2017. 9(1):1–12.
• doi:10.1109/JPHOT.2017.2651586.
• [17] Gu H, Wang Z, Zhang B, Yang Y, Wang K. Time-division-multiplexing–wavelength-division-
• multiplexing-based architecture for ONoC. Journal of Optical Communications and Networking, 2017.
• 9(5):351–363. doi:10.1364/JOCN.9.000351.
• [18] Yang Y, Chen K, Gu H, Zhang B, Zhu L. TAONoC: A regular passive optical network-on-chip
• architecture based on comb switches. IEEE Transactions on Very Large Scale Integration (VLSI)
• Systems, 2018. 27(4):954–963. doi:10.1109/TVLSI.2018.2885141.
• [19] Bose B, Broeg B, Kwon Y, Ashir Y. Lee distance and topological properties of k-ary n-cubes. IEEE
• Transactions on Computers, 1995. 44(8):1021–1030. doi:10.1109/12.403718.
• [20] Yang Y, Wang S. A note on Hamiltonian paths and cycles with prescribed edges in the 3-ary n-
• cube. Information Sciences, 2015. 296:42–45. doi:10.1016/j.ins.2014.10.034.
• [21] Gu MM, Hao RX. 3-extra connectivity of 3-ary n-cube networks. Information Processing Letters,
• 2014. 114(9):486–491.
• [22] Seitz CL. Submicron systems architecture project: Semiannual technical report. 1989.
• [23] Ashir Y, Stewart IA. Embeddings of cycles, meshes and tori in faulty k-ary n-cubes. In:
• Proceedings 1997 International Conference on Parallel and Distributed Systems. IEEE, 1997 pp. 429–
• 435. doi:10.1109/ICPADS.1997.652583.
• [24] Ashir YA, Stewart IA. Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes. SIAM
• Journal on Discrete Mathematics, 2002. 15(3):317–328. doi:10.1137/S08954801963111.
• [25] Bauer DW, Carothers CD. Scalable RF propagation modeling on the IBM Blue Gene/L and Cray
• XT5 supercomputers. In: Proceedings of the 2009 Winter Simulation Conference (WSC). IEEE, 2009
• pp. 779–787. doi:10.1109/WSC.2009.5429676.
• [26] Abu-Libdeh H, Costa P, Rowstron A, O’Shea G, Donnelly A. Symbiotic routing in future data
• centers. In: Proceedings of the ACM SIGCOMM 2010 conference. 2010 pp. 51–62.
• doi:10.1145/1851275.1851191.
• [27] Dong Q, Yang X, Wang D. Embedding paths and cycles in 3-ary n-cubes with faulty nodes and
• links. Information Sciences, 2010. 180(1):198–208. doi:10.1016/j.ins.2009.09.002.
• [28] Lv Y, Lin CK, Fan J, Jia X. Hamiltonian cycle and path embeddings in 3-ary n-cubes based on K1, 3-
• structure faults. Journal of Parallel and Distributed Computing, 2018. 120:148–158.
• doi:10.1016/j.jpdc.2018.06.007.
• [29] Fan WB, Fan JX, Lin CK, Wang Y, Han YJ, Wang RC. Optimally embedding 3-ary n-cubes into grids.
• Journal of Computer Science and Technology, 2019. 34(2):372–387. doi:10.1007/s11390-019-1893-0.
• [30] Fan W, Fan J, Zhang Y, Han Z, Chen G. Communication and performance evaluation of 3-ary n-
• cubes onto network-on-chips. Science China Information Sciences, 2022. 65(7):1–3.
• doi:10.1007/s11432-019-2794-9.
• [31] Fan W, He J, Han Z, Li P, Wang R. Reconfigurable Fault-tolerance mapping of ternary N-cubes
• onto chips. Concurrency and Computation: Practice and Experience, 2020. 32(11):e5659.
• doi::10.1002/cpe.5659.
• [32] Bezrukov SL, Das SK, Els¨asser R. An edge-isoperimetric problem for powers of the Petersen
• graph. Annals of Combinatorics, 2000. 4(2):153–169. doi:10.1007/s000260050003.
• [33] Bezrukov SL, Chavez JD, Harper LH, R¨ottger M, Schroeder UP. Embedding of hypercubes into
• grids. In: Mathematical Foundations of Computer Science 1998: 23rd International Symposium,
• MFCS’98 Brno, Czech Republic, August 24–28, 1998 Proceedings 23. Springer, 1998 pp. 693–701.
• doi:10.1007/BFb0055820.
• [34] Miller M, Rajan RS, Parthiban N, Rajasingh I. Minimum linear arrangement of incomplete
• hypercubes. The Computer Journal, 2015. 58(2):331–337. doi:10.1093/comjnl/bxu031.
• [35] Arockiaraj M, Manuel PD, Rajasingh I, Rajan B. Wirelength of 1-fault hamiltonian graphs into
• wheels and fans. Inf. Process. Lett., 2011. 111(18):921–925. doi:10.1016/j.ipl.2011.06.011.
• [36] Hsieh SY, Lin TJ, Huang HL. Panconnectivity and edge-pancyclicity of 3-ary n-cubes. The Journal
• of Supercomputing, 2007. 42(2):225–233. doi:10.1007/s11227-007-0133-5.
• [37] Bezrukov SL, Bulatovic P, Kuzmanovski N. New infinite family of regular edge-isoperimetric
• graphs. Theor. Comput. Sci., 2018. 721:42–53. doi:10.1016/j.tcs.2017.12.036.
• [38] Lindsey JH. Assignment of numbers to vertices. The American Mathematical Monthly, 1964.
• 71(5):508–516.
• [39] Harper L. A necessary condition on minimal cube numberings. Journal of Applied Probability,
• 1967. 4(2):397–401. doi:10.2307/3212033.
• [40] Ahlswede R, Cai N. General Edge-isoperimetric Inequalities, Part II: a Local-Global Principle for
• Lexicographical Solutions. Eur. J. Comb., 1997. 18(5):479–489. doi:10.1006/eujc.1996.0106.
• [41] Wijaya R, Semaniov-Feovkov A, Ryan J, Kalinowski T. H-supermagic labelings for firecrackers,
• banana trees and flowers. Australasian Journal of Combinatorics, 2017. 69:442–451.
• [42] Gallian J. A Survey: A dynamic survey on graph labeling. Electron. J. Combin, 2007.
• [43] Swaminathan V, Jeyanthi P. Super edge-magic strength of fire crackers, banana trees and
• unicyclic graphs. Discrete mathematics, 2006. 306(14):1624–1636. doi:10.1016/j.disc.2005.06.038.
• [44] Bezrukov S, Monien B, Unger W, Wechsung G. Embedding ladders and caterpillars into the
• hypercube. Discrete Applied Mathematics, 1998. 83(1-3):21–29. doi:10.1016/S0166-218X(97)00101-
• 7.
• [45] Manuel P, Arockiaraj M, Rajasingh I, Rajan B. Embedding hypercubes into cylinders, snakes and
• caterpillars for minimizing wirelength. Discrete Applied Mathematics, 2011. 159(17):2109–2116.
• doi:10.1016/j.dam.2011.07.003.
• [46] Haralambides J, Makedon F, Monien B. Bandwidth minimization: an approximation algorithm for
• caterpillars. Mathematical Systems Theory, 1991. 24(1):169–177. doi:10.1007/BF02090396.
• [47] Monien B. The bandwidth minimization problem for caterpillars with hair length 3 is NP-
• complete. SIAM Journal on Algebraic Discrete Methods, 1986. 7(4):505–512.
• [48] Chen WC, Lu HI, Yeh YN. Operations of interlaced trees and graceful trees. Southeast Asian Bull.
• Math, 1997. 21(4):337–348.
• [49] Wang Z, Gu H, Yang Y, Zhang H, Chen Y. An adaptive partition-based multicast routing scheme
• for mesh-based networks-on-chip. Computers & Electrical Engineering, 2016. 51:235–251.
• doi:10.1016/j.compeleceng.2016.01.021.
• [50] Sugumaran AK, Jayachandran E. Domination number of some graphs. 2018. ISSN: 2455-2631.
• [51] Rajasingh I, Rajan B, Rajan RS. Embedding of hypercubes into necklace, windmill and snake
• graphs. Information Processing Letters, 2012. 112(12):509–515. doi:10.1016/j.ipl.2012.03.006.
• [52] Bezrukov SL, Chavez JD, Harper LH, R¨ottger M, Schroeder U. Embedding of Hypercubes into
• Grids. In: Mathematical Foundations of Computer Science 1998, 23rd International Symposium,
• MFCS’98, Brno, Czech Republic, August 24-28, 1998, Proceedings, volume 1450 of Lecture Notes in
• Computer Science. Springer, 1998 pp. 693–701.
• [53] Manuel PD, Rajasingh I, Rajan B, Mercy H. Exact wirelength of hypercubes on a grid. Discret.
• Appl. Math., 2009. 157(7):1486–1495.
• [54] Bezrukov SL, Chavez JD, Harper LH, R¨ottger M, Schroeder U. The congestion of n-cube layout on
• a rectangular grid. Discret. Math., 2000. 213(1-3):13–19.
• [55] Carlson TA. The edge-isoperimetric problem for discrete tori. Discret. Math., 2002. 254(1-3):33–
• 49.
• [56] R¨ottger M, Schroeder UP. Efficient embeddings of grids into grids. Discrete Applied
• Mathematics, 2001. 108(1-2):143–173.
• [57] Opatrny J, Sotteau D. Embeddings of complete binary trees into grids and extended grids with
• total vertex-congestion 1. Discrete Applied Mathematics, 2000. 98(3):237–254.
• [58] Bezrukov SL. Embedding complete trees into the hypercube. Discrete Applied Mathematics,
• 2001. 110(2-3):101–119.
• [59] Caha R, Koubek V. Optimal embeddings of generalized ladders into hypercubes. Discrete
• Mathematics, 2001. 233(1-3):65–83.
• [60] Er M. Lexicographical Ordering of k-Subsets of a Set. Journal of Information and Optimization
• Sciences, 1986. 7(2):113–116.
• [61] Bollob´as B, Leader I. An Isoperimetric Inequality on the Discrete Torus. SIAM J. Discret. Math.,
• 1990. 3(1):32–37.
• [62] Lai P, Tsai C. Embedding of tori and grids into twisted cubes. Theor. Comput. Sci., 2010. 411(40-
• 42):3763–3773.
• [63] Fan J, Jia X. Embedding meshes into crossed cubes. Inf. Sci., 2007. 177(15):3151–3160.
• [64] Miller M, Rajan RS, Parthiban N, Rajasingh I. Minimum Linear Arrangement of Incomplete
• Hypercubes. Comput. J., 2015. 58(2):331–337.
• [65] Boals AJ, Gupta AK, Sherwani NA. Incomplete hypercubes: Algorithms and embeddings. J.
• Supercomput., 1994. 8(3):263–294.
• [66] L¨u L, Zhou T. Link prediction in complex networks: A survey. Physica A: statistical mechanics and
• its applications, 2011. 390(6):1150–1170.
• [67] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-
• Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7.284 S. Rajeshwari and M. Rajesh / Exact
• Wirelength of Embedding 3-Ary n-Cubes into certain Cylinders...
• [68] Harper L, Chavez J. Global methods of combinatorial optimization. Preprint, Cambridge
• University Press.
• [69] Harper LH. Optimal assignments of numbers to vertices. Journal of the Society for Industrial and
• Applied Mathematics, 1964. 12(1):131–135.
• [70] Hamdi M. Embedding hierarchical networks into the hypercube. In: Proceedings of 1994 37th
• Midwest Symposium on Circuits and Systems, volume 1. IEEE, 1994 pp. 302–305.
• [71] Choudum SA, Indhumathi R. On embedding subclasses of height-balanced trees in hypercubes.
• Information Sciences, 2009. 179(9):1333–1347.
• [72] Bezrukov SL. Edge isoperimetric problems on graphs. Graph Theory and Combinatorial Biology,
• 1999. 7:157–197.
• [73] L PN. Applications of Graph Labeling in Communication Networks. Orient. J. Comp. Sci. and
• Technol, 2014. 7(1).
• [74] Arkut IC, Arkut RC, Ghani N. Graceful label numbering in optical MPLS networks. In: Chlamtac I
• (ed.), OptiComm 2000: Optical Networking and Communications, volume 4233. 2000 pp. 1 – 8.
• [75] Goyal P, Ferrara E. Graph Embedding Techniques, Applications, and Performance: A Survey.
• Knowledge-Based Systems, 2017, doi:10.1016/j.knosys.2018.03.022.
• [76] Leighton FT. Introduction to parallel algorithms and architectures: Arrays· trees· hypercubes.
• Elsevier, 2014.
• [77] Jung-hyun S, HyeongOk L, Moon-suk J. Constructing complete binary trees on Petersen-torus
• networks. In: 2008 Third International Conference on Convergence and Hybrid Information
• Technology, volume 2. IEEE, 2008 pp. 252–255. doi:10.1109/ICCIT.2008.54.
• [78] Ramya M, Meenakshi S. Labeling Techniques of Some Special Graphs. International Journal of
• Pure and Applied Mathematics, 2017. 116(24):93–102. ISSN:1311-8080.
• [79] Day K, Al-Ayyoub AE. Fault diameter of k-ary n-cube networks. IEEE Transactions on Parallel and
• Distributed Systems, 1997. 8(9):903–907. doi:10.1109/71.615436.
• [80] Day K, Al-Ayyoub AE. Minimal fault diameter for highly resilient product networks. IEEE
• Transactions on Parallel and Distributed Systems, 2000. 11(9):926–930. doi:10.1109/71.879775.
• [81] Bae MM, Bose B. Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes. IEEE
• Transactions on Computers, 2003. 52(10):1271–1284. doi:10.1109/TC.2003.1234525.
• [82] Wang T, Su Z, Xia Y, Qin B, Hamdi M. NovaCube: A low latency Torus-based network architec-
• ture for data centers. In: 2014 IEEE Global Communications Conference. IEEE, 2014 pp. 2252–2257.
• doi:10.1109/GLOCOM.2014.7037143.