关于L_(∞)-模距离的二维带宽问题  

Two-Dimensional Bandwidth Problem under Distance of L_(∞)-Norm

作　　者：林诒勋[1] 郝建修[1] 李湘露[1] 

机构地区：[1]郑州大学数学系,郑州450052

出　　处：《运筹学学报》2000年第3期8-12,共5页Operations Research Transactions

基　　金：the National Natural Science Foundation of China (19771075).

摘　　要：二维带宽问题是将图Ｇ嵌入平面格子图，使其最长的连边尽可能短．迄今为止，在平面格子图中考虑的距离为矩线距离，即Ｌ１－模距离．在本文中，我们研究在Ｌ∞－模距离意义下的二维带宽问题．The two-dimensional bandwidth problem is to find an embedding of graph G in a grid graph in the plane such that the longest edges are as short as possible. The distance of the grid graph considered so far is the rectilinear distance, i.e., the distance of L1-norm. In this paper we study the problem under the distance of L-norm.

关 键 词：图的嵌入 二维带宽 L_(1)-模距离 L_(∞)-模距离 

分 类 号：O157.5[理学—数学]