Covering a set with arithmetic progressions is NP-complete

DOI10.1016/0020-0190(90)90013-NzbMath0695.68038OpenAlexW1941405594MaRDI QIDQ910219

Lenwood S. Heath

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90013-n

zbMATH Keywords

computational complexityset coveringNP-completearithmetic progressions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Discrete mathematics in relation to computer science (68R99)

Cites Work

• On sets of integers containing k elements in arithmetic progression
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Unnamed Item
• Unnamed Item

This page was built for publication: Covering a set with arithmetic progressions is NP-complete