The congestion of n-cube layout on a rectangular grid

被引：69

作者：

Bezrukov, SL ^{[1
]}

Chavez, JD

Harper, LH

Röttger, M

Schroeder, UP

机构：

[1] Univ Wisconsin, Dept Math & Comp Sci, Superior, WI 54880 USA

[2] Calif State Univ San Bernardino, Dept Math, San Bernardino, CA 92407 USA

[3] Univ Calif Riverside, Dept Math, Riverside, CA 92521 USA

[4] Univ Gesamthsch Paderborn, Dept Math & Comp Sci, D-33102 Paderborn, Germany

来源：

DISCRETE MATHEMATICS | 2000年 / 213卷 / 1-3期

关键词：

embedding; edge congestion; edge-isoperimetric problem; hypercubes; grids;

D O I：

10.1016/S0012-365X(99)00162-4

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider the problem of embedding the n-dimensional cube into a rectangular grid with 2(n) vertices in such a way as to minimize the congestion, the maximum number of edges along any point of the grid. After presenting a short solution for the cutwidth problem of the n-cube (in which the n-cube is embedded into a path), we show how to extend the results to give an exact solution for the congestion problem. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：13 / 19

页数：7