On some variants of the bandwidth minimization problem. (English) Zbl 0545.68058

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

SIAM J. Comput. 13, 650-667 (1984).

Summary: We 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. We show that the cycle- bandwidth problem is NP-complete for each fixed \(k\geq 2\), the separation and cycle-separation problems are both NP-complete for each \(k\geq 1\), and the directed separation problem is NP-complete for arbitrary k. We give polynomial time algorithms for several special cases of the directed separation problem. Finally we show the relationships of the directed separation problem with several scheduling problems by giving reductions among them.

MSC:

68R10	Graph theory (including graph drawing) in computer science
68Q25	Analysis of algorithms and problem complexity
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems

Keywords:

multiprocessor scheduling; directed graphs; forests; interval orders; bandwidth minimization; cycle-bandwidth; circular layout; separation; linear layout; cycle-separation; NP-complete; directed separation; polynomial time algorithms