树的费用全染色的近似算法

树的费用全染色的近似算法

陈勇^1,2

1. 山东大学数学与系统科学学院，山东济南250100；2. 济南大学理学院，山东济南250022

收稿日期:2005-06-09 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 陈勇

An approximate algorithm for the cost totalcoloring of trees

CHEN Yong^1,2

1. School of Math. and System Sci., Shandong Univ., Jinan 250100, Shandong, China;2. School of Sciences, Jinan Univ., Jinan 250022, Shandong, China

Received:2005-06-09 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: CHEN Yong^1,2

摘要/Abstract

摘要： 给定无向简单图G=(V,E)与颜色集C，并且对C中的每一种颜色c设定一个费用值w(c)∈R⁺.全染色是给出图的一个可行染色使得相关联的边和点、相邻的点或边都染不同的颜色.定义了费用全染色问题，即求解最优的全染色f，使得染色费用和最小，对于树图T，给出了一个2-近似算法，该算法的运行时间为O(nΔ²).

关键词: 边染色, 全染色, 树 , 费用全染色, 费用边染色, NP-hard

Abstract: Let G be a simple graph, C be a set of colors, and let w be a cost function which assigns a real number w(c) to each color c in C. A totalcoloring of a graph G is to color all the elements of V(G)∪E(G) in such a way that no two adjacent or incident elements receive the same color. A 2-approximate algorithm is given to find an optimal cost total-coloring of a given tree T, that is, a totalcoloring f of　T such that the sum of costs w(f(x)) of　colors f(x) assigned to all elements x is minimum among all total-colorings of T. The algorithm takes time O(nΔ²) if n is the number of vertices and Δ is the maximum degree of T.

Key words: tree , cost totalcoloring, cost edgecoloring, NP-hard, totalcoloring, edge coloring

中图分类号:

O224

陈勇, . 树的费用全染色的近似算法[J]. J4, 2006, 41(1): 111-114 .

CHEN Yong, . An approximate algorithm for the cost totalcoloring of trees[J]. J4, 2006, 41(1): 111-114 .

参考文献

相关文章 15

[1]	寇艳芳,陈祥恩,王治文. K1,3,p和 K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报（理学版）, 2018, 53(8): 53-60.
[2]	王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[3]	潘文华,徐常青. 一类稀疏图的邻和可区别边色数[J]. 山东大学学报（理学版）, 2017, 52(8): 94-99.
[4]	陈祥恩,苗婷婷,王治文. 两条路的联图的点可区别I-全染色[J]. 山东大学学报（理学版）, 2017, 52(4): 30-33.
[5]	何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[6]	王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报（理学版）, 2016, 51(8): 29-34.
[7]	李世玲, 陈祥恩,王治文. 完全二部图K3,n(n≥18)的点可区别E-全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 68-71.
[8]	谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78.
[9]	宋红杰,巩相男,潘文华,徐常青. Halin图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 65-67.
[10]	伊文慧,王延平,王华田,马雪松,王文波. 酚酸类化感物质对杨树人工林土壤硝化作用的影响[J]. 山东大学学报（理学版）, 2016, 51(1): 27-35.
[11]	马丽菲,莫倩,杜辉. 面向中文短影评的分类技术研究[J]. 山东大学学报（理学版）, 2016, 51(1): 52-57.
[12]	孟献青. 一类平面图的强边染色[J]. 山东大学学报（理学版）, 2015, 50(08): 10-13.
[13]	何雪, 田双亮. 若干图的倍图的邻点可区别边(全)染色[J]. 山东大学学报（理学版）, 2015, 50(04): 63-66.
[14]	李敬文, 贾西贝, 董威, 李小慧, 闫光辉. 图的邻点可区别全染色算法[J]. 山东大学学报（理学版）, 2015, 50(02): 14-21.
[15]	姚京京, 徐常青. 最大度为3或4的图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2015, 50(02): 9-13.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed