SOME VARIANTS OF THE BANDWIDTH MINIMIZATION PROBLEM.

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

doi:10.1137/0213040

SOME VARIANTS OF THE BANDWIDTH MINIMIZATION PROBLEM.

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

Research output: Contribution to journal › Article › peer-review

88 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 language	English (US)
Pages (from-to)	650-667
Number of pages	18
Journal	SIAM Journal on Computing
Volume	13
Issue number	3
DOIs	https://doi.org/10.1137/0213040
State	Published - 1984
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0213040

Cite this

@article{1fb351e298a049cc855e645215159c30,

title = "SOME VARIANTS OF THE BANDWIDTH MINIMIZATION PROBLEM.",

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.",

author = "Leung, {Joseph Y.T.} and Oliver Vornberger and Witthoff, {James D.}",

year = "1984",

doi = "10.1137/0213040",

language = "English (US)",

volume = "13",

pages = "650--667",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - SOME VARIANTS OF THE BANDWIDTH MINIMIZATION PROBLEM.

AU - Leung, Joseph Y.T.

AU - Vornberger, Oliver

AU - Witthoff, James D.

PY - 1984

Y1 - 1984

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0021471093&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021471093&partnerID=8YFLogxK

U2 - 10.1137/0213040

DO - 10.1137/0213040

M3 - Article

AN - SCOPUS:0021471093

SN - 0097-5397

VL - 13

SP - 650

EP - 667

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

SOME VARIANTS OF THE BANDWIDTH MINIMIZATION PROBLEM.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this