|
|||||
|
|
| 圈中t-区间的k-染色问题 | |
| 引用本文： | 李曙光,白淑岩,何志红,亓兴勤.圈中t-区间的k-染色问题[J].山东大学学报(理学版),2006,41(6):40-42. |
| 作者姓名： | 李曙光 白淑岩 何志红 亓兴勤 |
| 作者单位： | 1. 山东大学,数学与系统科学学院,山东,济南,250100;烟台大学,数学与信息科学学院,山东,烟台,264005 2. 烟台职业学院,基础教学部,山东,烟台,264000 3. 山东大学,数学与系统科学学院,山东,济南,250100 4. 山东大学,威海分校应用数学系,山东,威海,264209 |
| 基金项目： | 国家自然科学基金;天津市教委资助项目 |
| 摘 要： | 考虑客户请求在圈中实现的问题. 每个请求联系着一个t 区间, 由圈上至多t(t1)个区间构成. 要实现一个请求, 需选择它所对应的t 区间中的一个区间并为其安排k种颜色中的一种. 任意两个选定的区间如果在圈上有公共边, 则不能得到同一种颜色. 对目标寻求实现最大数目的请求问题, 给出了一个3.042 近似算法. |
| 关 键 词： | :圈 t-区间 k-染色 近似算法 |
| 文章编号： | 1671-9352（2006）06-0040-03 |
| 收稿时间： | 2005-12-19 |
| 修稿时间： | 2005年12月19 |
On the k-coloring of t-intervals in a cycle |
|
| LI Shu-guang,BAI Shu-yan,HE Zhi-hong,QI Xing-qin.On the k-coloring of t-intervals in a cycle[J].Journal of Shandong University,2006,41(6):40-42. | |
| Authors: | LI Shu-guang BAI Shu-yan HE Zhi-hong QI Xing-qin |
| Institution: | 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; Department of Applied Math., Shandong University at Weihai, Weihai 264209, Shandong, China |
| 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(t1) 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. |
| Keywords: | cycle t-intervals k-coloring approximation algorithms |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 | |
| 点击此处可从《山东大学学报(理学版)》下载免费的PDF全文 | |