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

被引：0

作者：

Rajalaxmi, T. M. ^{[1
]}

Parthiban, N. ^{[2
]}

Ryan, Joe ^{[3
]}

Shantrina, A. Arul ^{[4
]}

Rajan, R. Sundara ^{[4
]}

机构：

[1] SSN Coll Engn, Dept Math, Chennai 603110, Tamil Nadu, India

[2] SRM Inst Sci & Technol, Dept Comp Sci & Engn, Chennai 603203, Tamil Nadu, India

[3] Univ Newcastle, Sch Elect Engn & Comp, Callaghan, NSW 2308, Australia

[4] Hindustan Inst Technol & Sci, Dept Math, Chennai 603103, Tamil Nadu, India

来源：

DISCRETE MATHEMATICS LETTERS | 2020年 / 3卷

关键词：

embedding; wirelength; chord graph; necklace graph; windmill graph; EFFICIENT EMBEDDINGS; ARRANGEMENT; HYPERCUBES; TREES; GRIDS;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：50 / 56

页数：7

共 25 条

[1]

[Anonymous], 2006, Introduction to the Theory of Computation

[2] Embedding complete trees into the hypercube [J].

Bezrukov, SL .

DISCRETE APPLIED MATHEMATICS, 2001, 110 (2-3) :101-119

[3] EFFICIENT EMBEDDINGS OF TREES IN HYPERCUBES [J].

BHATT, SN ;

CHUNG, FRK ;

LEIGHTON, FT ;

ROSENBERG, AL .

SIAM JOURNAL ON COMPUTING, 1992, 21 (01) :151-162

[4] Optimal linear arrangements using betweenness variables [J].

Caprara, Alberto ;

Oswald, Marcus ;

Reinelt, Gerhard ;

Schwarz, Robert ;

Traversi, Emiliano .

MATHEMATICAL PROGRAMMING COMPUTATION, 2011, 3 (03) :261-280

[5] On embedding subclasses of height-balanced trees in hypercubes [J].

Choudum, S. A. ;

Indhumathi, R. .

INFORMATION SCIENCES, 2009, 179 (09) :1333-1347

[6]

Das S., 2000, Ann. Comb, V4, P153, DOI DOI 10.1007/S000260050003

[7] An efficient algorithm for embedding exchanged hypercubes into grids [J].

Fan, Weibei ;

Fan, Jianxi ;

Lin, Cheng-Kuan ;

Wang, Guijuan ;

Cheng, Baolei ;

Wang, Ruchuan .

JOURNAL OF SUPERCOMPUTING, 2019, 75 (02) :783-807

[8]

Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness

[9]

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

[10] Embedding of tori and grids into twisted cubes [J].

Lai, Pao-Lien ;

Tsai, Chang-Hsiung .

THEORETICAL COMPUTER SCIENCE, 2010, 411 (40-42) :3763-3773

← 1 2 3 →