• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
【24h】

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

机译：平面图，二部图和分割图上的加权着色：复杂度和逼近度

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

摘要

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that MIN WEIGHTED NODE COLORING is NP-hard in Pg-free bipartite graphs, but polynomial for P-5-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with MIN WEIGHTED EDGE COLORING in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6 - epsilon, for any epsilon > 0 and we give an approximation algorithm with the same ratio. Finally, we show that MIN WEIGHTED NODE COLORING in split graphs can be solved by a polynomial time approximation scheme.
机译：我们研究平面图，二分图和分裂图中的最小加权节点着色的复杂度和逼近度。我们证明，即使平面图中没有三角形且其最大程度在4之上，该问题在平面图中也是NP-hard的。然后，我们证明MIN WEIGHTED NODE COLORING在无Pg二部图中是NP-hard的，但是无P-5二部图的多项式。接下来，我们将重点放在一般二分图中的逼近度上，并通过提供与不可逼近范围匹配的逼近比来改善早期的逼近结果。接下来，我们将在二分图中处理“最小加权边缘着色”。我们表明，即使在输入图既是立方图又是平面图的情况下，此问题也仍然具有很强的NP难度。此外，对于任何大于0的epsilon，我们都提供了7/6-epsilon的不可逼近边界，并且给出了具有相同比率的近似算法。最后，我们证明了分裂图中的最小加权节点着色可以通过多项式时间逼近方案来求解。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号