...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >On-Line Dimension for Posets Excluding Two Long Incomparable Chains
【24h】

On-Line Dimension for Posets Excluding Two Long Incomparable Chains

机译：Posets的在线尺寸，不包括两条长无比链

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

摘要

For a positive integer k, let k + k denote the poset consisting of two disjoint k-element chains, with all points of one chain incomparable with all points of the other. Bosek, Krawczyk and Szczypka showed that for each k≥1, there exists a constant c_k so that First Fit will use at most c_kw~2 chains in partitioning a poset P of width at most w, provided the poset excludes k + k as a subposet. This result played a key role in the recent proof by Bosek and Krawczyk that 0(w~(16 log w)) chains are sufficient to partition on-line a poset of width w into chains. This result was the first improvement in Kierstead's exponential bound: (5~w-1)/4 in nearly 30 years. Subsequently, Joret and Milans improved the Bosek-Krawczyk-Szczypka bound for the performance of First Fit to 8(K - 1)~2w, which in turn yields the modest improvement to O(w~(14 log w)) for the general on-line chain partitioning result. In this paper, we show that this class of posets admits a notion of on-line dimension. Specifically, we show that when k and w are positive integers, there exists an integer t = t(k, w) and an on-line algorithm that will construct an on-line realizer of size t for any poset P having width at most w, provided that the poset excludes k + k as a subposet.
机译：对于正整数k，令k + k表示由两个不相交的k元素链组成的波塞，其中一个链的所有点都无法与另一个链的所有点相比。 Bosek，Krawczyk和Szczypka显示，对于每个k≥1，存在一个常数c_k，因此只要Fitt将k + k排除为a，First Fit将最多使用c_kw〜2条链来划分宽度w的姿势P。换位该结果在Bosek和Krawczyk的最新证明中扮演了关键角色，证明0（w〜（16 log w））链足以将宽度为w的摆锤在线分割为链。这一结果是基尔斯特德指数界的首次改进：（5〜w-1）/ 4是近30年以来的。随后，Joret和Milans将Bosek-Krawczyk-Szczypka的性能提高到First Fit达到8（K-1）〜2w，这反过来又使一般情况下的O（w〜（14 log w））有所改善。在线链划分结果。在本文中，我们证明了这类花样接受在线尺寸的概念。具体来说，我们表明，当k和w为正整数时，存在整数t = t（k，w），并且一种在线算法将构造一个宽度为t最多为最大的位姿P的在线实现器。 w，前提是波状图排除k + k作为子波状。

著录项

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

    Stefan Felsner; Tomasz Krawczyk; William T. Trotter;

  • 作者单位

    Institut fuer Mathematik, Technische Universitaet Berlin,Strasse des 17. Juni 136,10623 Berlin, Germany;

    Theoretical Computer Science, Faculty of Mathematics and Computer Science,Jagiellonian University, ui. prof. Stanislawa Lojasiewicza 6, 30-348, Krakow, Poland;

    School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA;

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

    On-line algorithm; Partially ordered set; Dimension;

    机译：在线算法;部分订购的套装;尺寸;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号