World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Minimum Linear Arrangement of the Cartesian Product of Optimal Order Graph and Path

    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. D. Adolphson, T. C. Hu, Optimal linear ordering, SIAM J. Appl. Math. 25(3) (1973) 403–423. Crossref, ISIGoogle Scholar
    • 2. D. L. Adolphson, Single machine job sequencing with precedence constraints, SIAM J. Comput. 6(1) (1977) 40–54. CrossrefGoogle Scholar
    • 3. R. Ahlswede, S. L. Bezrukov, Edge isoperimetric theorems for integer point arrays, Appl. Math. Lett. 8(2) (1995). 75–80. Crossref, ISIGoogle Scholar
    • 4. R. Ahlswede, N. Cai, General edge-isoperimetric inequalities, European J. Combin. 18 (1997) 355–372. Crossref, ISIGoogle Scholar
    • 5. M. Arockiaraj, J. Abraham, A. J. Shalini, Node set optimization of complete Josephus cubes, J. Comb. Optim. 38(4) (2019) 1180–1195. Crossref, ISIGoogle Scholar
    • 6. M. Arockiaraj, J. Abraham, J. Quadras, A. J. Shalini, Linear layout of locally twisted cubes, Int. J. Comput. Math. 94(1) (2017) 56–65. Crossref, ISIGoogle Scholar
    • 7. S. L. Bezrukov, S. K. Das, R. Elsässer, An edge-isoperimetric problem for powers of the Petersen graph, Ann. Comb. 4(2) (2000) 153–169. CrossrefGoogle Scholar
    • 8. S. L. Bezrukov, U.-P. Schroeder, The cyclic wirelength of trees, Discrete Appl. Math. 87(1–3) (1998) 275–277. Crossref, ISIGoogle Scholar
    • 9. A. J. Boals, A. K. Gupta, N. A. Sherwani, Incomplete hypercubes: Algorithms and embeddings, J. Supercomput. 8(3) (1994) 263–294. Crossref, ISIGoogle Scholar
    • 10. H.-L. Chen, N.-F. Tzeng, A boolean expression-based approach for maximum incomplete subcube identification in faulty hypercubes, IEEE Trans. Parallel Distrib. Syst. 8(11) (1997) 1171–1183. Crossref, ISIGoogle Scholar
    • 11. F. R. K. Chung, On optimal linear arrangements of trees, Comput. Math. Appl. 10(1) (1984) 43–60. Crossref, ISIGoogle Scholar
    • 12. J. Cohen, F. Fomin, P. Heggernes, D. Kratsch, G. Kucherov, Optimal linear arrangement of interval graphs, in Mathematical Foundations of Computer Science 2006 (Springer, Berlin Heidelberg, 2006), pp. 267–279. CrossrefGoogle Scholar
    • 13. J. Ďiaz, J. Petit, M. Serna, A survey of graph layout problems, ACM Comput. Surv. 34(3) (2002) 313–356. Crossref, ISIGoogle Scholar
    • 14. M. Eikel, C. Scheideler, A. Setzer, 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. G. N. Fredrickson, S. E. Hambrusch, Planar linear arrangements of outerplanar graphs, IEEE Trans. Circuits Systems 35 (1988) 323–332. Crossref, ISIGoogle Scholar
    • 16. M. R. Garey, D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). Google Scholar
    • 17. A. K. Gupta, A. J. Boals, N. A. Sherwani, S. E. Hambrusch, A lower bound on embedding large hypercubes into small hypercubes, Congr. Numer. 78 (1990) 141–151. Google Scholar
    • 18. L. H. Harper, Global Methods for Combinatorial Isoperimetric Problems (Cambridge University Press, 2004). CrossrefGoogle Scholar
    • 19. L. H. Harper, Optimal assignments of numbers to vertices, SIAM J. Appl. Math. 12(1) (1964) 131–135. Crossref, ISIGoogle Scholar
    • 20. L. H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Comb. Theory 1(3) (1966) 385–393. CrossrefGoogle Scholar
    • 21. W. Imrich, S. Klavžar, D. F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product (CRC Press, Wellesley, Massachussets, 2008). CrossrefGoogle Scholar
    • 22. M. Juvan, B. Mohar, Optimal linear labelings and eigenvalues of graphs, Discrete Appl. Math. 36 (1992) 153–168. Crossref, ISIGoogle Scholar
    • 23. J. H. Lindsey, Assignment of numbers to vertices, Amer. Math. Monthly 71(5) (1964) 508–516. Crossref, ISIGoogle Scholar
    • 24. J. Liu, K. Williams, On bandwidth and edgesum for the composition of two graphs, Discrete Math. 143 (1995) 159–166. Crossref, ISIGoogle Scholar
    • 25. P. K. K. Loh, W. J. Hsu, Fault-tolerant routing for complete Josephus cubes, Parallel Comput. 30(9-10) (2004) 1151–1167. Crossref, ISIGoogle Scholar
    • 26. P. Manuel, I. Rajasingh, B. Rajan, H. Mercy, Exact wirelength of hypercubes on a grid, Discrete Appl. Math. 157 (2009) 1486–1495. Crossref, ISIGoogle Scholar
    • 27. M. Miller, R. S. Rajan, N. Parthiban, I. Rajasingh, Minimum linear arrangement of incomplete hypercubes, Comput. J. 58(2) (2015) 331–337. Crossref, ISIGoogle Scholar
    • 28. G. Mitchison, R. Durbin, Optimal numberings of an n × n array, SIAM J. Discrete Math. 7(4) (1986) 571–582. Crossref, ISIGoogle Scholar
    • 29. D. O. Muradyan, T. E. Piliposjan, 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. D. O. Muradyan, Minimal numberings of a two-dimensional cylinder (in Russian), Akad. Nauk. Armjan. SSR. Dokl. 75(3) (1982) 114–119. Google Scholar
    • 31. I. Rajasingh, M. Arockiaraj, Linear wirelength of folded hypercubes, Math. Comput. Sci. 5(1) (2011) 101–111. CrossrefGoogle Scholar
    • 32. I. Rajasingh, R. Sundara Rajan, P. Manuel, A linear time algorithm for embedding christmas trees into certain trees, Parallel Process. Lett. 25(4) (2015) 1550008 (17 pages). Link, ISIGoogle Scholar
    • 33. P. Raoufi, H. Rostami, H. Bagherinezhad, An optimal time algorithm for minimum linear arrangement of chord graphs, Inform. Sci. 238 (2013) 212–220. Crossref, ISIGoogle Scholar
    • 34. Y. Shiloach, A minimum linear arrangement algorithm for undirected trees, SIAM J. Comput. 8 (1979) 15–32. Crossref, ISIGoogle Scholar
    • 35. V. Sunitha, Augmented Cube: A New Interconnection Network, Ph.D. dissertation, Indian Institute of Technology, Madras, India, 2002. Google Scholar
    • 36. C. Zhou, Y. Pan, Y. Yang, Critical spanning tree and linear arrangement of torus, South Asian J. Math. 2(2) (2012) 88–96. Google Scholar