圈中t-区间的k-染色问题

圈中t-区间的k-染色问题

李曙光^1,2,白淑岩³,何志红¹,亓兴勤⁴

1. 山东大学数学与系统科学学院，山东济南250100； 2. 烟台大学数学与信息科学学院，山东烟台2640053. 烟台职业学院基础教学部，山东烟台264000； 4. 山东大学威海分校应用数学系，山东威海264209

收稿日期:2005-12-20 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 李曙光

On the kcoloring of tintervals in a cycle

LI Shu-guang,BAI Shu-yan,HE Zhi-hong,QI Kai-yuan

1. School of Math. and System Sci., Shandong Univ. , Jinan 250100, Shandong, China; 2. School of Math. and Info. Sci., Yantai Univ., Yantai 264005, Shandong, China;3. Division of Basic Courses, Yantai Vocational College, Yantai 264000, Shandong, China

Received:2005-12-20 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: LI Shu-guang

摘要/Abstract

摘要： 考虑客户请求在圈中实现的问题. 每个请求联系着一个t区间, 由圈上至多t(t1)个区间构成. 要实现一个请求, 需选择它所对应的t区间中的一个区间并为其安排k种颜色中的一种. 任意两个选定的区间如果在圈上有公共边, 则不能得到同一种颜色. 对目标寻求实现最大数目的请求问题, 给出了一个3.042近似算法.

关键词: :圈, t-区间, 近似算法 , k-染色

Abstract: The problem satisfying the clients requests in a given cycle is considered. Each request is associated with a tinterval, which consists of up to t(t1) intervals on the cycle. To satisfy a request, one of the intervals defining it must be selected and one of k colors must be assigned . No intervals selected for the requests can be assigned with the same color if they shared an edge of the cycle. A 3.042approximation algorithm is presented for the objective of maximizing the total number of satisfied requests.

Key words: approximation algorithms , kcoloring, tintervals, cycle

李曙光,白淑岩,何志红,亓兴勤 . 圈中t-区间的k-染色问题[J]. J4, 2006, 41(6): 40-42 .

LI Shu-guang,BAI Shu-yan,HE Zhi-hong,QI Kai-yuan . On the kcoloring of tintervals in a cycle[J]. J4, 2006, 41(6): 40-42 .

参考文献

相关文章 9

[1]	蔡裕华,魏凤英*. 度量空间的概率近似算法[J]. J4, 2013, 48(09): 51-55.
[2]	杨朝霞 . 超图嵌入带权重圈的一个2-近似算法[J]. J4, 2008, 43(8): 11-13 .
[3]	杨振光,李曙光,王秀红 . 工件尺寸不同的并行机批调度问题[J]. J4, 2007, 42(4): 63-66 .
[4]	戴珍香,李曙光,亓兴勤 . 波分复用星形单跳网中3信道的传输调度问题[J]. J4, 2007, 42(2): 46-50 .
[5]	亓兴勤,曹静,张晨 . 环型二元序列的赋权对换排序问题[J]. J4, 2007, 42(12): 46-48 .
[6]	李曙光,杨振光,何志红 . 多纤波分复用链网与环网中的利润极大化问题[J]. J4, 2006, 41(5): 7-11 .
[7]	王继强, . 一类median问题的近似算法研究[J]. J4, 2006, 41(4): 1-03 .
[8]	李曙光,亓兴勤,何志红 . 环网络中的呼叫接纳控制[J]. J4, 2006, 41(4): 15-19 .
[9]	亓兴勤,何志红,赵洪銮 . 二元序列的赋权对换排序问题[J]. J4, 2006, 41(1): 82-85 .

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed