|
|||||
|
|
On the complexity of constructing Golomb Rulers |
|
| Authors: | Christophe Meyer |
| Institution: | a GERAD, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal (Québec) H3T 2A7, Canada b Department of Computer Science, University of Toronto, 10 King’s College Road, Toronto, ON M5S 3G4, Canada |
| 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  -completeness results for two such decision problems. |
| Keywords: | Golomb Ruler Finite _method=retrieve& _eid=1-s2 0-S0166218X08003053& _mathId=si2 gif& _pii=S0166218X08003053& _issn=0166218X& _acct=C000053510& _version=1& _userid=1524097& md5=bd955f0353e06bd39daf174b46aee8bd')" style="cursor:pointer |
| 本文献已被 ScienceDirect 等数据库收录！ | |