| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427630 | Information Processing Letters | 2010 | 5 Pages |
Abstract
The two-dimensional bandwidth problem is to embed a graph G into an n×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 L1-norm distance and L∞-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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
