On the complexity of constructing Golomb Rulers

Meyer C; Papakonstantinou PA

首页> 外文期刊>Discrete Applied Mathematics >On the complexity of constructing Golomb Rulers

【24h】

On the complexity of constructing Golomb Rulers

机译：论构造哥伦布尺子的复杂性

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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.

机译：哥伦布尺子是带有整数标记的标尺，其中每两个标记之间的距离是不同的。哥伦布标尺在计算机科学和电气工程中有多种应用。据我们所知，与哥隆尺子有关的问题的计算复杂性是未知的。我们提供了与构建这样的标尺有关的问题的自然定义。这项工作的主要贡献是针对两个这样的决策问题的NP完全性结果。

著录项

来源
《Discrete Applied Mathematics》 |2009年第4期|共11页
作者
Meyer C; Papakonstantinou PA;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
Golomb Ruler; Finite B-2 set; NP-hardness;

机译：Golomb尺;有限B-2套;NP硬度;

相似文献

外文文献
中文文献
专利

1. On the complexity of constructing Golomb Rulers [J] . Meyer C, Papakonstantinou PA Discrete Applied Mathematics . 2009,第4期

机译：论构造哥伦布尺子的复杂性
2. A CONJECTURE ON A CONTINUOUS OPTIMIZATION MODEL FOR THE GOLOMB RULER PROBLEM [J] . Duxbury Phil, Lavor Carlile, de Salles-Neto Luiz Leduino RAIRO operations research . 2021,第4期

机译：Golomb统治者问题的连续优化模型猜想
3. A Comparative Study of Nature-Inspired Metaheuristic Algorithms in Search of Near-to-optimal Golomb Rulers for the FWM Crosstalk Elimination in WDM Systems [J] . Bansal Shonak Applied Artificial Intelligence . 2019,第12a14期

机译：自然启发型血管算法的比较研究，寻求WDM系统FWM串扰消除FWM串扰的近乎最优戈尔族统治者
4. On asymptotic complexity of the optimum Golomb ruler problem: From established stochastic methods to self-avoiding walks [C] . Franc Brglez, Borko Bošković, Janez Brest IEEE Congress on Evolutionary Computation . 2017

机译：最佳Golomb尺子问题的渐近复杂性：从建立的随机方法到自我避免的游走
5. Seeing Like a Farmer: Socioecological Complexity of Constructing and Maintaining Ecologically Integrated Smallholder Family Farms [D] . Bhattarai, Anil. 2019

机译：看像一个农民：社会心态复杂性构建和维护生态综合的小农家庭农场
6. Motivation rulers for smoking cessation: a prospective observational examination of construct and predictive validity [O] . Edwin D Boudreaux, Ashley Sullivan, Beau Abar, 2012

机译：戒烟的动机标尺：结构和预测有效性的前瞻性观察检查
7. On the complexity of constructing Golomb Rulers [O] . Meyer Christophe, Papakonstantinou Periklis A. 2009

机译：论构造哥伦布尺子的复杂性
8. Complexity Construct in Political Psychology: Personological and Cognitive Approaches [R] . Suedfeld, P. 2010

机译：政治心理学中的复杂性构建：人格与认知方法

On the complexity of constructing Golomb Rulers

摘要

著录项

相似文献

相关主题

期刊订阅