Two models of two-dimensional bandwidth problems

被引：7
|
作者：
Lin, Lan [2 ,3 ]
Lin, Yixun [1 ]
机构：
[1] Zhengzhou Univ, Dept Math, Zhengzhou 450052, Peoples R China
[2] Tongji Univ, Key Lab Embedded Syst & Serv Comp, Minist Educ, Shanghai 200092, Peoples R China
[3] Tongji Univ, Sch Elect & Informat Engn, Shanghai 200092, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 11期
关键词：
Graph algorithms; Two-dimensional bandwidth; Lower bound; Upper bound; Optimal embedding; GRAPH LAYOUT PROBLEMS; VLSI LAYOUTS;
D O I：
10.1016/j.ipl.2010.04.013
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The two-dimensional bandwidth problem is to embed a graph G into an n x n grid in the plane such that the maximum distance between adjacent vertices is as small as possible. Here, the "distance" has two different meanings: the L-1-norm distance and L-infinity-norm distance. So we have two models of two-dimensional bandwidth problem. This paper investigates the basic properties and relations of these two models. Some lower bounds, upper bounds, and exact results are presented. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：469 / 473
页数：5
相关论文
共 50 条
12345