On the complexity of constructing Golomb rulers

DOI10.1016/j.dam.2008.07.006zbMath1186.68221OpenAlexW2080125678WikidataQ56083330 ScholiaQ56083330MaRDI QIDQ1028469

Periklis A. Papakonstantinou, Christophe Meyer

Publication date: 30 June 2009

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

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

zbMATH Keywords

Golomb ruler\(\mathbf {NP}\)-hardnessfinite B\(_2\) set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items

The S-canon and the multi-S-canon: an introduction ⋮ Unnamed Item ⋮ Exploiting a hypergraph model for finding Golomb rulers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partial digest is hard to solve for erroneous input data
• On the uniform distribution in residue classes of dense sets of integers with distinct sums
• On sum sets of Sidon sets. I
• The chords' problem
• PRIMES is in P
• Optimal recovery schemes in fault tolerant distributed computing
• The complexity of minimum difference cover
• Some necessary clarifications about the chords' problem and the partial digest problem
• Equivalence of some LP-based lower bounds for the Golomb ruler problem
• A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler
• Finding finite 𝐵₂-sequences faster
• A class of binary recurrent codes with limited error propagation
• GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA