Top

Published in:

2017 | OriginalPaper | Chapter

Optimal Embedding of Locally Twisted Cubes into Grids

Authors : Jessie Abraham, Micheal Arockiaraj

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The hypercube has been used in numerous problems related to interconnection networks due to its simple structure and communication properties. The locally twisted cube is an important class of hypercube variants with the same number of nodes and connections per node, but has only half the diameter and better graph embedding capability as compared to its counterpart. The embedding problem plays a significant role in parallel and distributed systems. In this paper we devise an optimal embedding of the n-dimensional locally twisted cube onto a grid network.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Polynomial Time Algorithms for Bichromatic Problems

Arockiaraj, M., Abraham, J., Quadras, J., Shalini, A.J.: Linear layout of locally twisted cubes. Int. J. Comput. Math. (2015). doi:10.1080/00207160.2015.1088943

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. 4, 235–282 (1994)MathSciNetCrossRefMATH

Bezrukov, S.L., Chavez, J.D., Harper, L.H., Röttger, M., Schroeder, U.-P.: The congestion of \(n\)-cube layout on a rectangular grid. Discret. Math. 213(1), 13–19 (2000)MathSciNetCrossRefMATH

Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comp. Syst. Sci. 28, 300–343 (1984)MathSciNetCrossRefMATH

Djidjev, H.N., Vrto, I.: Crossing numbers and cutwidths. J. Graph Algorithms Appl. 7, 245–251 (2003)MathSciNetCrossRefMATH

Han, H., Fan, J., Zhang, S., Yang, J., Qian, P.: Embedding meshes into locally twisted cubes. Inform. Sci. 180, 3794–3805 (2010)MathSciNetCrossRefMATH

Harper, L.H.: Optimal assignments of numbers to vertices. J. Soc. Ind. Appl. Math. 12, 131–135 (1964)MathSciNetCrossRefMATH

Harper, L.H.: Global Methods for Combinatorial Isoperimetric Problems. Cambridge University Press, London (2004)CrossRefMATH

Lai, Y.L., Williams, K.: A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs. J. Graph Theory 31, 75–94 (1999)MathSciNetCrossRefMATH

10.

Manuel, P., Rajasingh, I., Rajan, B., Mercy, H.: Exact wirelength of hypercube on a grid. Discret. Appl. Math. 157(7), 1486–1495 (2009)MathSciNetCrossRefMATH

11.

Opatrny, J., Sotteau, D.: Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1. Discret. Appl. Math. 98, 237–254 (2000)MathSciNetCrossRefMATH

12.

Rajasingh, I., Arockiaraj, M.: Linear wirelength of folded hypercubes. Math. Comput. Sci. 5, 101–111 (2011)MathSciNetCrossRefMATH

13.

Rajasingh, I., Arockiaraj, M., Rajan, B., Manuel, P.: Minimum wirelength of hypercubes into n-dimensional grid networks. Inform. Process. Lett. 112, 583–586 (2012)MathSciNetCrossRefMATH

14.

Rajasingh, I., Rajan, R.S., Parthiban, N., Rajalaxmi, T.M.: Bothway embedding of circulant network into grid. J. Discret. Algorithms. 33, 2–9 (2015)MathSciNetCrossRefMATH

15.

Yang, X., Evans, D.J., Megson, G.M.: The locally twisted cubes. Int. J. Comput. Math. 82(4), 401–413 (2005)MathSciNetCrossRefMATH

Title: Optimal Embedding of Locally Twisted Cubes into Grids
Authors: Jessie Abraham
Micheal Arockiaraj
Publisher: Springer International Publishing
Book: Algorithms and Discrete Applied Mathematics
Print ISBN: 978-3-319-53006-2

Electronic ISBN: 978-3-319-53007-9

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-53007-9_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner