✦ LIBER ✦

The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete

✍ Scribed by David Muradian

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 323 KB
Volume: 307
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(03)00238-x

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we show that the bandwidth minimization problem remains NP-complete for cyclic caterpillars with hair length 1. Cyclic caterpillars with hair length 1 are graphs in which the removal of all pendant vertices results in a simple cycle.