Duality in Bandwidth Problems

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

*Corresponding author for this work

Research output: Contribution to journalJournal article


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 languageEnglish
Pages (from-to)117-127
Number of pages11
JournalCongressus Numerantium
Publication statusPublished - Dec 1997

User-Defined Keywords

  • Bandwidth
  • Duality


Dive into the research topics of 'Duality in Bandwidth Problems'. Together they form a unique fingerprint.

Cite this