• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >Partitioning Posets
【24h】

Partitioning Posets

机译：划分词组

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

摘要

Given a poset P = (X, <), a partition X_1,..., X_k of X is called an ordered partition of P if, whenever x ∈X_i and y e X_j with x < y, then i ≤ j. In this paper, we show that for every poset P = (X, <) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m -1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, m/k - c(k)m~(1/2), for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, -<) and an integer 2 ≤ k ≤ ∣X∣, we can find an ordered partition of P into A: parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results.
机译：给定一个位姿P =（X，<），如果每当x∈x_y和y e X_j且x

著录项

  • 来源
    《Order》 |2008年第2期|p.131-152|共22页
  • 作者

    Viresh Patel;

  • 作者单位

    Department of Mathematics, London School of Economics, Houghton Street, London, WC2A 2AE, UK;

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

    posets; partitions; cuts;

    机译：坐姿;分区;切口;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号