A note on the hardness of Skolem-type sequences

DOI10.1016/J.DAM.2010.01.006MaRDI QIDQ972331zbMATH OpenOpenAlexFDO

Authors Gustav Nordh

Publication date 25 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.01.006

zbMATH Keywords

Skolem sequence\(\mathbf{NP}\)-completenesscoupled task scheduling

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Other designs, configurations (05B30) Special sequences and polynomials (11B83)

Recommendations

• \(\mathcal{NP}\)-completeness of generalized multi-Skolem sequences
• Extended skolem sequences
• Perfect Skolem sets
• scientific article; zbMATH DE number 1151811
• scientific article; zbMATH DE number 2192143

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 682566 (Why is no real title available?)
• Extended Langford sequences with small defects
• Extended skolem sequences
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• On certain distributions of integers in pairs with given differences
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Perfect Skolem sets
• The complexity of completing partial Latin squares
• The existence of (p,q)-extended Rosa sequences
• \(\mathcal{NP}\)-completeness of generalized multi-Skolem sequences

Cited in

(4)

• The existence of two new classes of near-Skolem type sequences
• \(\mathcal{NP}\)-completeness of generalized multi-Skolem sequences
• scientific article; zbMATH DE number 3981175 (Why is no real title available?)
• The intersection spectrum of hooked Skolem sequences and applications

This page was built for publication: A note on the hardness of Skolem-type sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972331)