The Bandwidth Minimization Problem is NP-complete for lobsters and k-polygon graphs

• Author(s) / Creator(s)

  • Morgan, David

• Technical report TR05-02. Assmann et al. [SIAM J. Alg. Disc. Meth., 2 (1981), 387-393] have shown that the bandwidth of caterpillars on n vertices with hairs of length at most two can be found in O(n log n) time and Monien [SIAM J. Alg. Disc. Meth., 7 (1986), 505-512] has shown that Bandwidth Minimization remains NP-complete when restricted to caterpillars with hair length at most three. In this work it is shown that Bandwidth Minimization remains NP-complete when restricted to lobsters, despite the existing polynomial algorithms for this problem on their modules and prime decompositions. Additionally, we show the problem to be NP-complete on k-polygon graphs, for all k ≥ 3. | TRID-ID TR05-02

• Date created

  2005

• Subjects / Keywords

  • Bandwidth Minimization
  • $k$-polygon graph
  • Computational complexity
  • Prime decomposition
  • Lobster

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3JD4PQ43

• License

  Attribution 3.0 International