On the complexity of constructing Golomb rulers

DOI10.1016/J.DAM.2008.07.006MaRDI QIDQ1028469zbMATH OpenOpenAlexWikidataFDO

Authors Christophe Meyer, Periklis A. Papakonstantinou

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

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

Mathematics Subject Classification ID

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

Recommendations

• Exploiting a hypergraph model for finding Golomb rulers
• Exploiting a Hypergraph Model for Finding Golomb Rulers
• A conjecture on a continuous optimization model for the Golomb ruler problem
• A Lagrangian Relaxation for Golomb Rulers
• Golomb rulers

Cites work

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

Cited in

(13)

• A review of the available construction methods for Golomb rulers
• A computational comparison of optimization methods for the Golomb ruler problem
• Equivalence of some LP-based lower bounds for the Golomb ruler problem
• The S-canon and the multi-S-canon: an introduction
• Golomb rulers
• Exploiting a Hypergraph Model for Finding Golomb Rulers
• Some new disjoint Golomb rulers
• Exploiting a hypergraph model for finding Golomb rulers
• There Are No New Homometric Golomb Ruler Pairs with 12 Marks or Less
• A conjecture on a continuous optimization model for the Golomb ruler problem
• scientific article; zbMATH DE number 7650083 (Why is no real title available?)
• Results on the graceful game and range-relaxed graceful game
• Partial reformulation-linearization based optimization models for the Golomb ruler problem

This page was built for publication: On the complexity of constructing Golomb rulers

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