ERA

Download the full-sized PDF of The Bandwidth Minimization Problem is NP-complete for lobsters and k-polygon graphsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3JD4PQ43

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

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

Descriptions

Author or creator
Morgan, David
Additional contributors
Subject/Keyword
Bandwidth Minimization
Lobster
Prime decomposition
$k$-polygon graph
Computational complexity
Type of item
Computing Science Technical Report
Computing science technical report ID
TR05-02
Language
English
Place
Time
Description
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.
Date created
2005
DOI
doi:10.7939/R3JD4PQ43
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-29T18:49:33.000+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 548908
Last modified: 2015:10:12 17:16:20-06:00
Filename: TR05-02.pdf
Original checksum: 0752ba021c5cdfc65114960c5033daf9
Well formed: true
Valid: true
Page count: 14
Activity of users you follow
User Activity Date