Usage
  • 22 views
  • 188 downloads

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

  • Author(s) / Creator(s)
  • 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
  • Type of Item
    Report
  • DOI
    https://doi.org/10.7939/R3JD4PQ43
  • License
    Attribution 3.0 International