• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory and application of models of computation >Incremental List Coloring of Graphs Parameterized by Conservation
【24h】

Incremental List Coloring of Graphs Parameterized by Conservation

机译：通过守恒参数化的图形的增量列表着色

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

摘要

Incrementally k-list coloring a graph means that a graph is given by adding stepwise one vertex after another, and for each intermediate step we ask for a vertex coloring such that each vertex has one of the colors specified by its associated list containing some of in total k colors. We introduce the "conservative version" of this problem by adding a further parameter c € N specifying the maximum number of vertices to be recolored between two subsequent graphs (differing by one vertex). This "conservation parameter" c models the natural quest for a modest evolution of the coloring in the course of the incremental process instead of performing radical changes. We show that the problem is NP-hard for k ≥ 3 and W[l]-hard when parameterized by c. In contrast, the problem becomes fixed-parameter tractable with respect to the combined parameter (k, c). We prove that the problem has an exponential-size kernel with respect to (k, c) and there is no polynomial-size kernel unless NP coNP/poly. Finally, we provide empirical findings for the practical relevance of our approach in terms of an effective graph coloring heuristic.
机译：递增k-list为图形着色意味着通过逐步添加一个顶点给另一个图形来给出图形，并且对于每个中间步骤，我们要求一个顶点着色，以使每个顶点具有由其关联列表指定的一种颜色，其中包含总共k种颜色。通过添加另一个参数c€N来指定此问题的“保守版本”，该参数指定要在两个后续图形之间进行重着色的最大顶点数量（相差一个顶点）。该“保护参数” c模拟了在增量过程中进行适度的着色而不是进行根本性改变的自然追求。我们表明，当用c进行参数化时，对于k≥3的问题是NP-困难的，而对w [l]的问题是困难的。相反，该问题对于组合参数（k，c）变为固定参数易处理的。我们证明问题相对于（k，c）具有指数大小的核，除非NP coNP / poly，否则没有多项式大小的核。最后，根据有效的图形着色启发式方法，我们为我们的方法的实际相关性提供了经验性发现。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号