...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >The Arboreal Jump Number of an Order
【24h】

The Arboreal Jump Number of an Order

机译：订单的树状跳转编号

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

摘要

Let Ρ bea partial order and A an arboreal extension of it (i.e. the Hasse diagram of A is a rooted tree with a unique minimal element). A jump of A is a relation contained in the Hasse diagram of A, but not in the order P. The arboreal jump number of A is the number of P jumps contained in it. We study the problem of finding the arboreal extension of having minimum arboreal jump number-a problem related to the well-known (linear) jump number problem.We describe several result for this problem,including NP-completeness,polynomial time solvable cases and bounds. We also discuss the concept of a minimal arboreal extension, namely an arboreal extension whose removal of one jump makes it no longer arboreal.
机译：令P为部分顺序，A为树的扩展（即A的Hasse图是具有唯一最小元素的根树）。 A的跳跃是A的哈西图中包含的一个关系，但不是P的顺序。A的树状跳跃数是其中包含的P跳跃的数目。我们研究寻找具有最小树突跳数的树突扩展的问题-一个与众所周知的（线性）跳数问题有关的问题。我们描述了该问题的几种结果，包括NP完备性，多项式时间可解情况和界限。我们还讨论了最小树状扩展名的概念，即树状扩展名，其消除了一个跳转使其不再成为树状扩展。

著录项

  • 来源
    《Order》 |2013年第1期|339-350|共12页
  • 作者

    Adriana P. Figueiredo; Michel Habib; Sulamita Klein; Jayme Luiz Szwarcfiter;

  • 作者单位

    DME, Universidade Federal do Estado do Rio de Janeiro, Rio de Janeiro, Brazil;

    LIAFA, Universite Paris Diderot - Paris 7, Paris, France CNRS, Universite Paris Diderot - Paris 7, Paris, France;

    IM, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil;

    IM, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil NCE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil;

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

    Arboreal jump number; Order extensions; Greedy chain decompositions; Jump number; Partially ordered sets;

    机译：树木跳数;订单扩展;贪婪的链分解;跳数;部分订购的套装;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号