Minimum Linear Arrangement of the Cartesian Product of Optimal Order Graph and Path
Abstract
The minimum linear arrangement of an arbitrary graph is the embedding of the vertices of the graph onto the line topology in such a way that the sum of the distances between adjacent vertices in the graph is minimized. This minimization can be attained by finding an optimal ordering of the vertex set of the graph and labeling the vertices of the line in that order. In this paper, we compute the minimum linear arrangement of the Cartesian product of certain sequentially optimal order graphs which include interconnection networks such as hypercube, folded hypercube, complete Josephus cube and locally twisted cube with path and the edge faulty counterpart of sequentially optimal order graphs.
References
- 1. , Optimal linear ordering, SIAM J. Appl. Math. 25(3) (1973) 403–423. Crossref, ISI, Google Scholar
- 2. , Single machine job sequencing with precedence constraints, SIAM J. Comput. 6(1) (1977) 40–54. Crossref, Google Scholar
- 3. , Edge isoperimetric theorems for integer point arrays, Appl. Math. Lett. 8(2) (1995). 75–80. Crossref, ISI, Google Scholar
- 4. , General edge-isoperimetric inequalities, European J. Combin. 18 (1997) 355–372. Crossref, ISI, Google Scholar
- 5. , Node set optimization of complete Josephus cubes, J. Comb. Optim. 38(4) (2019) 1180–1195. Crossref, ISI, Google Scholar
- 6. , Linear layout of locally twisted cubes, Int. J. Comput. Math. 94(1) (2017) 56–65. Crossref, ISI, Google Scholar
- 7. , An edge-isoperimetric problem for powers of the Petersen graph, Ann. Comb. 4(2) (2000) 153–169. Crossref, Google Scholar
- 8. , The cyclic wirelength of trees, Discrete Appl. Math. 87(1–3) (1998) 275–277. Crossref, ISI, Google Scholar
- 9. , Incomplete hypercubes: Algorithms and embeddings, J. Supercomput. 8(3) (1994) 263–294. Crossref, ISI, Google Scholar
- 10. , A boolean expression-based approach for maximum incomplete subcube identification in faulty hypercubes, IEEE Trans. Parallel Distrib. Syst. 8(11) (1997) 1171–1183. Crossref, ISI, Google Scholar
- 11. , On optimal linear arrangements of trees, Comput. Math. Appl. 10(1) (1984) 43–60. Crossref, ISI, Google Scholar
- 12. ,
Optimal linear arrangement of interval graphs , in Mathematical Foundations of Computer Science 2006 (Springer, Berlin Heidelberg, 2006), pp. 267–279. Crossref, Google Scholar - 13. , A survey of graph layout problems, ACM Comput. Surv. 34(3) (2002) 313–356. Crossref, ISI, Google Scholar
- 14. ,
Minimum linear arrangement of series-parallel graphs , in Approximation and Online Algorithms,Lecture Notes in Computer Science (Springer International Publishing, Wrocław, Poland, 2014), pp. 168–180. Google Scholar - 15. , Planar linear arrangements of outerplanar graphs, IEEE Trans. Circuits Systems 35 (1988) 323–332. Crossref, ISI, Google Scholar
- 16. , Computers and Intractability, A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). Google Scholar
- 17. , A lower bound on embedding large hypercubes into small hypercubes, Congr. Numer. 78 (1990) 141–151. Google Scholar
- 18. , Global Methods for Combinatorial Isoperimetric Problems (Cambridge University Press, 2004). Crossref, Google Scholar
- 19. , Optimal assignments of numbers to vertices, SIAM J. Appl. Math. 12(1) (1964) 131–135. Crossref, ISI, Google Scholar
- 20. , Optimal numberings and isoperimetric problems on graphs, J. Comb. Theory 1(3) (1966) 385–393. Crossref, Google Scholar
- 21. , Topics in Graph Theory: Graphs and Their Cartesian Product (CRC Press, Wellesley, Massachussets, 2008). Crossref, Google Scholar
- 22. , Optimal linear labelings and eigenvalues of graphs, Discrete Appl. Math. 36 (1992) 153–168. Crossref, ISI, Google Scholar
- 23. , Assignment of numbers to vertices, Amer. Math. Monthly 71(5) (1964) 508–516. Crossref, ISI, Google Scholar
- 24. , On bandwidth and edgesum for the composition of two graphs, Discrete Math. 143 (1995) 159–166. Crossref, ISI, Google Scholar
- 25. , Fault-tolerant routing for complete Josephus cubes, Parallel Comput. 30(9-10) (2004) 1151–1167. Crossref, ISI, Google Scholar
- 26. , Exact wirelength of hypercubes on a grid, Discrete Appl. Math. 157 (2009) 1486–1495. Crossref, ISI, Google Scholar
- 27. , Minimum linear arrangement of incomplete hypercubes, Comput. J. 58(2) (2015) 331–337. Crossref, ISI, Google Scholar
- 28. , Optimal numberings of an array, SIAM J. Discrete Math. 7(4) (1986) 571–582. Crossref, ISI, Google Scholar
- 29. , The problem of finding the length and width of the complete p-partite graph (in Russian), Uchen. Zapiski Erevan. Gosunivers. 144(2) (1980) 18–26. Google Scholar
- 30. , Minimal numberings of a two-dimensional cylinder (in Russian), Akad. Nauk. Armjan. SSR. Dokl. 75(3) (1982) 114–119. Google Scholar
- 31. , Linear wirelength of folded hypercubes, Math. Comput. Sci. 5(1) (2011) 101–111. Crossref, Google Scholar
- 32. , A linear time algorithm for embedding christmas trees into certain trees, Parallel Process. Lett. 25(4) (2015) 1550008 (17 pages). Link, ISI, Google Scholar
- 33. , An optimal time algorithm for minimum linear arrangement of chord graphs, Inform. Sci. 238 (2013) 212–220. Crossref, ISI, Google Scholar
- 34. , A minimum linear arrangement algorithm for undirected trees, SIAM J. Comput. 8 (1979) 15–32. Crossref, ISI, Google Scholar
- 35. V. Sunitha, Augmented Cube: A New Interconnection Network, Ph.D. dissertation, Indian Institute of Technology, Madras, India, 2002. Google Scholar
- 36. , Critical spanning tree and linear arrangement of torus, South Asian J. Math. 2(2) (2012) 88–96. Google Scholar


