A note on the hardness of Skolem-type sequences
2010 (English)In: DISCRETE APPLIED MATHEMATICS, ISSN 0166-218X, Vol. 158, no 8, 964-966 p.Article in journal (Refereed) Published
The purpose of this note is to give upper bounds (assuming P different from NP) on how far the generalizations of Skolem sequences can be taken while still hoping to resolve the existence question. We prove that the existence questions for both multi-Skolem sequences and generalized Skolem sequences are strongly NP-complete. These results are significant strengthenings and simplifications of the recent NP-completeness result for generalized multi-Skolem sequences.
Place, publisher, year, edition, pages
Elsevier Science B.V., Amsterdam. , 2010. Vol. 158, no 8, 964-966 p.
Skolem sequence, NP-completeness, Coupled task scheduling
IdentifiersURN: urn:nbn:se:liu:diva-56302DOI: 10.1016/j.dam.2010.01.006ISI: 000276941800010OAI: oai:DiVA.org:liu-56302DiVA: diva2:318303