...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Efficient algorithms for decomposing graphs under degree constraints
【24h】

Efficient algorithms for decomposing graphs under degree constraints

机译：在度约束下分解图的高效算法

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

摘要

Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321-324] proved that if every vertex v in a graph G has degree d (v) >= a (v) + b(v) + I (where a and b are arbitrarily given nonnegative integer-valued functions) then G has a nontrivial vertex partition (A, B) such that d(A) (v) >= a (v) for every v is an element of A and d(B) (v) >= b(v) for every v is an element of B. Kaneko [On decomposition of triangle-free graphs under degree constraints, J. Graph Theory 27 (1998) 7-91 and Diwan [Decomposing graphs with girth at least five under degree constraints, J. Graph Theory 33 (2000) 237-239] strengthened this result, proving that it suffices to assume d(v) >= a + b (a, b >= 1) or just d(v) >= a + b - 1 (a, b >= 2) if G contains no cycles shorter than 4 or 5, respectively. The original proofs contain nonconstructive steps. In this paper we give polynomial-time algorithms that find such partitions. Constructive general izati ons for k-partitions are also presented. (c) 2006 Elsevier B.V. All rights reserved.
机译：Stiebitz [在度约束下分解图，J。图论23（1996）321-324]证明，如果图G中的每个顶点v的度为d（v）> = a（v）+ b（v）+ I（其中a和b被任意赋予非负整数值函数），则G具有非平凡的顶点分区（A，B），使得每个v的d（A）（v）> = a（v）是A和d的元素（B）（v）> = b（v），每个v是B的元素。Kaneko [关于度约束下无三角图的分解，J。图论27（1998）7-91和Diwan [分解图J. Graph Theory 33（2000）237-239]的周长至少为5，J.Graph Theory 33（2000）237-239]加强了这一结果，证明足以假设d（v）> = a + b（a，b> = 1）或仅如果G不包含分别短于4或5的循环，则d（v）> = a + b-1（a，b> = 2）。原始证明包含非建设性步骤。在本文中，我们给出了找到这种划分的多项式时间算法。还介绍了k分区的构造性通用izati。 （c）2006 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号