• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Algorithms and Computation(ISAAC 2004); 20041220-22; Hong Kong(CN) >Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation
【24h】

Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation

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

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

摘要

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-complete 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-complete in P_8-free bipartite graphs, but polynomial for P_5-free bipartite graphs. We next focus ourselves 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-complete, even in the case where the input-graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6 - ε, for any ε > 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完全的。然后，我们证明MIN WEIGHTED NODE COLORING在无P_8的二部图中是NP完全的，但是无P_5的二部图的多项式。接下来，我们将注意力集中在一般二部图上的逼近度，并通过给出与不可逼近范围匹配的逼近比来改善早期的逼近结果。接下来，我们将在二分图中处理“最小加权边缘着色”。我们表明，即使在输入图既是立方图又是平面图的情况下，该问题也仍然具有很强的NP完整性。此外，对于任何ε> 0，我们提供了7/6-ε的不可逼近界，并且给出了具有相同比率的近似算法。最后，我们证明了分裂图中的最小加权节点着色可以通过多项式时间逼近方案来求解。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号