• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Parallel and Distributed Computing and Networks >SELF-STABILIZING ACYCLIC COLORINGS OF GRAPHS
【24h】

SELF-STABILIZING ACYCLIC COLORINGS OF GRAPHS

机译：自稳定的无环花色

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

摘要

This paper proposes two self-stabilizing algorithms for acyclic colorings of graphs. An acyclic coloring of a graph G is a coloring of the vertices of G such that the vertices with the same color in G induces an acyclic subgraph. The first algorithm we proposed needs 2 colors for a complete bipartite graph, or less than 1+D/2 colors for a general graph, where D is the degree of G. Both graphs must be acyclic oriented in advance. In some special acyclic orientation, it needs only 3 colors for a planar graph, or a K3,3-free or K5-free graph. The second algorithm we proposed is for a K4-free and rooted graph, and it needs only 2 colors.
机译：针对图的非循环着色，本文提出了两种自稳定算法。图G的非循环着色是G顶点的着色，以使G中具有相同颜色的顶点产生非循环子图。我们提出的第一个算法对于一个完整的二部图需要2种颜色，对于一般图则需要少于1 + D / 2种颜色，其中D是G的度数。两个图都必须事先无环取向。在某些特殊的非循环定向中，平面图或无K3,3或无K5的图只需要3种颜色。我们提出的第二种算法是针对无K4且有根的图，它仅需要两种颜色。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号