...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Optimization >Probabilistic graph-coloring in bipartite and split graphs
【24h】

Probabilistic graph-coloring in bipartite and split graphs

机译：二部图和分裂图的概率图着色

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

摘要

We revisit in this paper the stochastic model for minimum graph-coloring introduced in (Murat and Paschos in Discrete Appl. Math. 154:564–586, 2006), and study the underlying combinatorial optimization problem (called probabilistic coloring) in bipartite and split graphs. We show that the obvious 2-coloring of any connected bipartite graph achieves standard-approximation ratio 2, that when vertex-probabilities are constant probabilistic coloring is polynomial and, finally, we propose a polynomial algorithm achieving standard-approximation ratio 8/7. We also handle the case of split graphs. We show that probabilistic coloring is NP-hard, even under identical vertex-probabilities, that it is approximable by a polynomial time standard-approximation schema but existence of a fully a polynomial time standard-approximation schema is impossible, even for identical vertex-probabilities, unless P=NP. We finally study differential-approximation of probabilistic coloring in both bipartite and split graphs.
机译：我们在本文中再次探讨了最小图形着色的随机模型（Murat和Paschos in Discrete Appl。Math。154：564–586，2006），并研究了二分法和拆分法中潜在的组合优化问题（称为概率着色）图。我们表明，任何连通二分图的明显2色均达到标准近似比2，当顶点概率恒定时，概率着色为多项式，最后，我们提出了一种实现标准近似比为8/7的多项式算法。我们还处理分割图的情况。我们表明，即使在相同的顶点概率下，概率着色也是NP-hard的，它可以由多项式时间标准近似方案近似，但是即使对于相同的顶点概率，也不可能存在完全的多项式时间标准近似方案，除非P = NP。我们最终研究了二部图和分裂图中概率色的微分逼近。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号