LATTICE BANDWIDTH OF RANDOM GRAPHS

被引：2

作者：

MCDIARMID, C ^{[1
]}

MILLER, Z ^{[1
]}

机构：

[1] MIAMI UNIV,DEPT MATH & STAT,OXFORD,OH 45056

来源：

DISCRETE APPLIED MATHEMATICS | 1991年 / 30卷 / 2-3期

关键词：

D O I：

10.1016/0166-218X(91)90046-Y

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The bandwidth of a random graph has been well studied. A natural generalization of bandwidth involves replacing the path as host graph by a multi-dimensional lattice. In this paper we investigate the corresponding behavior for random graphs.

引用

页码：221 / 227

页数：7

共 17 条

[1]

BERTOLAZZI P, 1983, GRID EMBEDDING PROBL, V2

[2]

BHATT S, 1983, UNPUB COMPLEXITY MIN

[3] THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].

BOLLOBAS, B .

COMBINATORICA, 1988, 8 (01) :49-55

[4]

Bollobas B., 1985, RANDOM GRAPHS

[5]

DELAVEGA WF, 1983, ANN DISCRETE MATH, V17, P633

[6]

ERDOS P, 1985, GRAPH THEORY SANDBJE

[7] COMPLEXITY RESULTS FOR BANDWIDTH MINIMIZATION [J].

GAREY, MR ;

GRAHAM, RL ;

JOHNSON, DS ;

KNUTH, DE .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1978, 34 (03) :477-495

[8]

KUANG Y, 1985, ARS COMBINATORIA, V20A, P29

[9]

LEIGHTON FT, UNPUB SIMULATING PYR

[10]

LEIGHTON FT, 1984, J COMPUT SYST SCI, V28, P300

← 1 2 →