A linear time algorithm for embedding chord graphs into certain necklace and windmill graphs

T. M. Rajalaxmi; N. Parthiban; Joe Ryan; A. Arul Shantrinal; R. Sundara Rajan

Author(s)

T. M. Rajalaxmi Department of Mathematics, SSN College of Engineering,Chennai 603 110,India

N. Parthiban Department of Computer Science and Engineering, SRM Institute of Science and Technology,Chennai 603 203,India

Joe Ryan School of Electrical Engineering and Computing, University of Newcastle,NSW 2308,Australia

A. Arul Shantrinal Department of Mathematics, Hindustan Institute of Technology and Science,Chennai 603 103,India

R. Sundara Rajan Department of Mathematics, Hindustan Institute of Technology and Science,Chennai 603 103,India

Abstract

Wirelength is a salient feature to authenticate the quality of an embedding of a guest graph into a host graph and is used specifically in Very Large Scale Integration (VLSI) layout designs. The chord graph is an influential topology in the sphere of peer-to-peer networks. Thus, it is interesting to study the embedding of chord graphs into networks. In this paper, we have computed the exact wirelength of chord graphs into necklace and windmill graphs. Further, we have developed a linear time algorithm to compute the wirelength.

Publication Details

Page(s) 50-56

DOI DOI not available

Published Journal: Discrete Mathematics Letters, Volume: 3, Issue: 0, Year: 2020

Request the full text from PASTIC

Keywords

chord graph, embedding, windmill graph, wirelength, necklace graph

References

Garey M. R.,Johnson D. S. .1979 .Computers and Intractability: A Guide to the Theory of NP-Completeness. , : .

Harper L. H. .2004 .. Global Methods for Combinatorial Isoperimetric Problems, : .

Lai P. L.,Tsai C. H. .2010 .Embedding of tori and grids into twisted cubes. Theor. Comput. Sci, 411 : 3763-3773.

J-B. Liu M.,Arockiaraj J. N.,Delaila J. N. .2019 .Wirelength of enhanced hypercube into windmill and necklace graphs. Mathematics, 7(5) : 383-392.

Manuel P.,Rajasingh I.,Rajan B.,Mercy H. .2009 .Exact wirelength of hypercube on a grid, Discrete Appl. , 157 : 1486-1495.

Miller M.,Rajan R. S.,Parthiban N.,I. Rajasingh N. .2015 .Minimum linear arrangement of incomplete hypercubes, Comput. , 58 : 331-337.

Parthiban N.,Ryan J.,I. Rajasingh J.,Rajan R. S.,Rani L. N. .2017 .Exact wirelength of embedding chord graph into tree-based architectures. Int. J. Netw. Virtual Organisations, 17 : 76-87.

Rajan R. S.,Rajalaxmi T. M.,Liu J. B. .2018 .Wirelength of embedding complete multipartite graphs into certain graphs. Discrete Appl, 05 : .

Rajan R. S.,Rajalaxmi T. M.,Ryan J.,Miller M.,Rushi Kumar,Sivaraj R.,Prasad B.,Nalliah M.,A M. .2019 .Improved bound for dilation of an embedding onto circulant networks. Applied Mathematics and Scientific Computing, : 623-632.

Rajan R. S.,Kalinowski T.,Rajalaxmi T. M. .2019 .Lower bounds for dilation, wirelength and edge congestion of embedding graphs into hypercubes. , : .

Rajasingh I.,Rajan B.,Rajan R. S. .2012 .Embedding of hypercubes into necklace, windmill and snake graphs, Inform. , 112(12) : 509-515.

Raoufi P.,Rostami H.,Bagherinezhad H. .2013 .An optimal time algorithm for minimum linear arrangement of chord graphs. Inform. Sci, 238 : 212-220.

Rostami H.,Habibi J. .2008 .Minimum linear arrangement of chord graphs. Appl. Math. Comput, 203 : 358-367.

Rottger M.,Schroeder U. P. .2001 .Efficient embeddings of grids into grids. Discrete Appl. Math, 108 : 143-173.

J. P. I. Silvestre .1998 .Approximation heuristics and benchmarkings for the MinLA problem. Proceedings of Algorithms and Experiments (ALEX'98): Building Bridges Between Theory and Applications, (11) : 112-128.

Sipser M. .2006 .. Theory of Computation, : .

I. Stoica ,Morris R.,Nowell D. L.,Karger D. R.,Kaashoek M. F.,Dabek F.,Balakrishnan H. .2003 .Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw, 11 : 17-32.

Xu J. .2001 .. Topological Structure and Analysis of Interconnection Networks, : .

Yu C.,Yao D.,Li X.,Zhang Y.,Yang L. T.,Xiong N.,Jin H. .2013 .Location-aware private service discovery in pervasive computing environment. Inform. Sci, 230 : 78-93.