## 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 | |

State | Published - 1984 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics