• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithms and Computation; Lecture Notes in Computer Science; 4288 >Flexible Word Design and Graph Labeling
【24h】

Flexible Word Design and Graph Labeling

机译：灵活的文字设计和图形标签

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Motivated by emerging applications for DNA code word design, we consider a generalization of the code word design problem in which an input graph is given which must be labeled with equal length binary strings of minimal length such that the Hamming distance is small between words of adjacent nodes and large between words of non-adjacent nodes. For general graphs we provide algorithms that bound the word length with respect to either the maximum degree of any vertex or the number of edges in either the input graph or its complement. We further provide multiple types of recursive, deterministic algorithms for trees and forests, and provide an improvement for forests that makes use of randomization.
机译：受新兴的DNA代码字设计应用程序的启发，我们考虑了代码字设计问题的一般化，其中给出了一个输入图，该图必须用等长的最小长度的等长二进制字符串标记，以使相邻单词之间的汉明距离很小节点和非相邻节点的单词之间较大。对于一般图形，我们提供了将字长限制为输入图或其补码中任何顶点的最大程度或边数的范围的算法。我们进一步为树木和森林提供了多种类型的递归确定性算法，并通过使用随机化对森林进行了改进。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号