| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419749 | Discrete Applied Mathematics | 2009 | 11 Pages |
Abstract
A Golomb Ruler is a ruler with integer marks where the distances between every two marks are distinct. Golomb Rulers find diverse applications in computer science and electrical engineering. According to our knowledge the computational complexity of problems related to the construction of Golomb Rulers is unknown. We provide natural definitions for problems related to the construction of such rulers. The main contribution of this work is NP-completeness results for two such decision problems.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Christophe Meyer, Periklis A. Papakonstantinou,