A note on the hardness of Skolem-type sequences

DOI10.1016/j.dam.2010.01.006zbMath1232.05046OpenAlexW2035130077MaRDI QIDQ972331

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

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

Related Items (1)

The intersection spectrum of hooked Skolem sequences and applications

Cites Work

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

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