SOME VARIANTS OF THE BANDWIDTH MINIMIZATION PROBLEM.

Joseph Y.T. Leung, Oliver Vornberger, James D. Witthoff

Research output: Contribution to journalArticlepeer-review

79 Scopus citations

Abstract

The authors consider the following variants of the bandwidth minimization problem: (1) the cycle-bandwidth problem which for a given graph G and positive integer k, asks if there is a circular layout such that every pair of adjacent vertexes have a distance at most k, (2) the separation problem which asks if there is a linear layout such that every pair of adjacent vertexes have a distance greater than k, and (3) the cycle-separation problem which asks if there is a circular layout such that every pair of adjacent vertexes have a distance greater than k. They show that the cycle-bandwidth problem is NP-complete for each fixed k greater than equivalent to 2, the separation and cycle-separation problems are both NP-complete for each fixed k greater than equivalent to 1, and the directed separation problem is NP-complete for arbitrary k. They give polynomial time algorithms for several special cases of the directed separation problem.

Original languageEnglish (US)
Pages (from-to)650-667
Number of pages18
JournalSIAM Journal on Computing
Volume13
Issue number3
DOIs
StatePublished - 1984

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'SOME VARIANTS OF THE BANDWIDTH MINIMIZATION PROBLEM.'. Together they form a unique fingerprint.

Cite this