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.
|Number of pages||11|
|Publication status||Published - Dec 1997|