图的对偶带宽问题(英文)

The Dual Bandwidth Problem for Graphs

图 G的带宽问题的一般提法是 :将图 G嵌入于主图 H,使得 G的边的最大跨度达到最小 .当图 G表示一种冲突关系时 ,便提出如下的对偶问题 :将图 G嵌入于主图 H,使得边的最小跨度达到最大 .研究了对偶带宽问题的基本性质和计算复杂性 .

The bandwidth problem of a graph G is to embed G into a host graph H such that the maximum stretch of the edges of G is minimized. In case of graph G representing a conflict relation, the following dual problem is proposed: to embed G into a host graph H such that the minimum stretch of the edges of G is maximized. An introductory study of the dual bandwidth problem is presented.