首页> 外文会议>Algorithms - ESA 2009 >Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
【24h】

Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard

机译:从水平和垂直投影重建三色网格是NP难的

获取原文
获取原文并翻译 | 示例

摘要

We consider the problem of coloring a grid using k colors with the restriction that in each row and each column has an specific number of cells of each color. In an already classical result, Ryser obtained a necessary and sufficient condition for the existence of such a coloring when two colors are considered. This characterization yields a linear time algorithm for constructing such a coloring when it exists. Gardner et al. showed that for k ≥ 7 the problem is NP-hard. Afterward Chrobak and Diirr improved this result, by proving that it remains NP-hard for k ≥ 4. We solve the gap by showing that for 3 colors the problem is already NP-hard. Besides we also give some results on tiling tomography.
机译:我们考虑了使用k种颜色为网格着色的问题,其限制是在每一行和每一列中每种颜色都有特定数量的单元格。在已经很经典的结果中,当考虑两种颜色时,Ryser获得了存在这种颜色的必要和充分条件。这种表征产生了线性时间算法,用于在存在这种颜色时构造这种颜色。 Gardner等。结果表明,对于k≥7,问题是NP难的。随后,Chrobak和Diirr证明了k≥4仍然保持NP难处理,从而改善了此结果。我们通过显示3种颜色的问题已经是NP困难的方法解决了这一差距。此外,我们还提供了有关切片层析成像的一些结果。

著录项

  • 来源
    《Algorithms - ESA 2009》|2009年|776-787|共12页
  • 会议地点 Copenhagen(DK);Copenhagen(DK);Copenhagen(DK)
  • 作者单位

    CNRS, LIX (UMR 7161), Ecole Polytechnique, 91128 Palaiseau, France;

    DIM, Universidad de Chile, Casilla 170-3, Correo 3, Santiago, Chile;

    DIM and CMM (UMI 2807, CNRS), Universidad de Chile,Casilla 170-3, Correo 3, Santiago, Chile;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算技术、计算机技术;
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号