-
题名边覆盖染色问题的有效算法
被引量:1
- 1
-
-
作者
陈琴
-
机构
中国计量学院理学院
-
出处
《中国科学:数学》
CSCD
北大核心
2016年第3期351-370,共20页
-
文摘
设G=(V,E)是一个重图.若边子集F的导出子图是G的一个生成子图,则称F为G的一个边覆盖.G的边覆盖色数ξ(G)是使得G可划分的最大不交边覆盖数.用δ(G)表示G的最小阶,令ρ(G)=min{2|?(U)|/(|U|+1):U?V(G),|U|≥3为奇数},其中?(U)表示至少有一个端点在U中的边集合.显然,ξ(G)≤min{δ(G),「ρ(G)」}.本文证明了,对系列平行重图和近似二部重图,此处等号成立,并且通过证明得到计算这两类重图的边覆盖色数的多项式时间算法.
-
关键词
边覆盖染色
系列平行重图
近似二部重图
-
Keywords
edge cover coloring
series-parallel multigraph
nearly bipartite multigraph
-
分类号
O157.5
[理学—基础数学]
-