Duality in Bandwidth Problems

Peter Che Bor Lam; Wai Chee Shiu; Yixun Lin

Duality in Bandwidth Problems

Peter Che Bor Lam^*, Wai Chee Shiu, Yixun Lin

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article

Abstract

The bandwidth is an important invariant in graph theory. However, the problem to determine the bandwidth of a general graph is NP-complete. To get sharp bounds, we propose to pay attention to various duality properties or minimax relations related to the bandwidth problems. This paper presents a study of this point of view.

Original language	English
Pages (from-to)	117-127
Number of pages	11
Journal	Congressus Numerantium
Volume	124
Publication status	Published - Dec 1997

User-Defined Keywords

Bandwidth
Duality

Cite this

@article{6293e2bc47fc49d7bacc2fbed60b266b,

title = "Duality in Bandwidth Problems",

abstract = "The bandwidth is an important invariant in graph theory. However, the problem to determine the bandwidth of a general graph is NP-complete. To get sharp bounds, we propose to pay attention to various duality properties or minimax relations related to the bandwidth problems. This paper presents a study of this point of view.",

keywords = "Bandwidth, Duality",

author = "Lam, {Peter Che Bor} and Shiu, {Wai Chee} and Yixun Lin",

note = "Funding information: This work is partially supported by the Hong Kong Baptist University Faculty Research Grant.",

year = "1997",

month = dec,

language = "English",

volume = "124",

pages = "117--127",

journal = "Congressus Numerantium",

issn = "0384-9864",

publisher = "Utilitas Mathematica Publishing",

}

TY - JOUR

T1 - Duality in Bandwidth Problems

AU - Lam, Peter Che Bor

AU - Shiu, Wai Chee

AU - Lin, Yixun

N1 - Funding information: This work is partially supported by the Hong Kong Baptist University Faculty Research Grant.

PY - 1997/12

Y1 - 1997/12

N2 - The bandwidth is an important invariant in graph theory. However, the problem to determine the bandwidth of a general graph is NP-complete. To get sharp bounds, we propose to pay attention to various duality properties or minimax relations related to the bandwidth problems. This paper presents a study of this point of view.

AB - The bandwidth is an important invariant in graph theory. However, the problem to determine the bandwidth of a general graph is NP-complete. To get sharp bounds, we propose to pay attention to various duality properties or minimax relations related to the bandwidth problems. This paper presents a study of this point of view.

KW - Bandwidth

KW - Duality

M3 - Journal article

SN - 0384-9864

VL - 124

SP - 117

EP - 127

JO - Congressus Numerantium

JF - Congressus Numerantium

ER -

Duality in Bandwidth Problems

Abstract

User-Defined Keywords

Fingerprint

Cite this