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

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 |