A note on the hardness of Skolem-type sequences

DOI10.1016/J.DAM.2010.01.006zbMATH Open1232.05046OpenAlexW2035130077MaRDI QIDQ972331FDOQ972331

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

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

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)

Cites Work

• Title not available (Why is that?)
• On certain distributions of integers in pairs with given differences
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• The complexity of completing partial Latin squares
• Extended skolem sequences
• The existence of \((p,q)\)-extended Rosa sequences
• 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
• Perfect Skolem sets
• Title not available (Why is that?)

Cited In (4)

• The existence of two new classes of near-Skolem type sequences
• \(\mathcal{NP}\)-completeness of generalized multi-Skolem sequences
• Title not available (Why is that?)
• 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)