• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >The Complexity of Embedding Orders into Small Products of Chains
【24h】

The Complexity of Embedding Orders into Small Products of Chains

机译：将订单嵌入到链的小产品中的复杂性

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

摘要

Embedding a partially ordered set into a product of chains is a classical way to encode it. Such encodings have been used in various fields such as object oriented programming or distributed computing. The embedding associates with each element a sequence of integers which is used to perform comparisons between elements. A critical measure is the space required by the encoding, and several authors have investigated ways to minimize it, which comes to embedding partially ordered sets into small products of chains. The minimum size of such an encoding has been called the encoding dimension (Habib et al. 1995), and the string dimension (Garg and Skawratananand 2001) for a slightly different definition of embeddings. This paper investigates some new properties of the encoding dimension. We clear up the links with the string dimension and we answer the computational complexity questions raised in Garg and Skawratananand (2001) and Habib et al. (1995): both these parameters are NP-hard to compute.
机译：将部分有序集嵌入到链的乘积中是一种经典的编码方式。这样的编码已经在各种领域中使用，例如面向对象的编程或分布式计算。嵌入与每个元素关联一个整数序列，该整数序列用于在元素之间执行比较。关键的措施是编码所需的空间，一些作者研究了最小化编码的方法，即将部分有序集嵌入到链的小产品中。这种编码的最小尺寸被称为编码尺寸（Habib等，1995），而字符串尺寸（Garg和Skawratananand 2001）则用于嵌入的定义稍有不同。本文研究了编码维度的一些新属性。我们用字符串维度清理链接，并回答Garg和Skawratananand（2001）以及Habib等人提出的计算复杂性问题。 （1995年）：这两个参数都是NP难以计算的。

著录项

  • 来源
    《Order》 |2010年第3期|p.365-381|共17页
  • 作者

    Olivier Raynaud; Eric Thierry;

  • 作者单位

    LIMOS, Universite Blaise Pascal, Campus des Cezeaux, Clermont-Ferrand, France;

    rnLIAFA, Universit e Paris 7 & LIP, ENS Lyon, France;

  • 收录信息 美国《科学引文索引》(SCI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    partially ordered sets; encodings; optimization;

    机译：部分订购的套装;编码;优化;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号