| 最小-最大圈划分的近似算法 |
| |
| 引用本文： | 邱保建,李敏,刘坚. 最小-最大圈划分的近似算法[J]. 山东大学学报(理学版), 2005, 40(6): 22-26,30 |
| |
| 作者姓名： | 邱保建 李敏 刘坚 |
| |
| 作者单位： | 济南大学,理学院,山东,济南,250022;山东轻工业学院,电子信息与控制工程学院,山东,济南,250100 |
| |
| 摘 要： | 给出了求解最小-最大圈划分问题的一种新的近似算法，该算法的近似比为305p-2，时间复杂性为O（n^4）．
|
| 关 键 词： | 近似算法 哈密尔顿圈 最小-最大圈划分 |
| 文章编号： | 1671-9352（2005）06-0022-05 |
| 收稿时间： | 2004-09-21 |
| 修稿时间： | 2004-09-21 |
An approximation algorithm for min-max cycle partition |
| |
| QIU Bao-jian,LI Min,LIU Jian. An approximation algorithm for min-max cycle partition[J]. Journal of Shandong University, 2005, 40(6): 22-26,30 |
| |
| Authors: | QIU Bao-jian LI Min LIU Jian |
| |
| Affiliation: | 1.School of Sciences, Jinan University, Jinan 250022, Shandong, China; 2. College of Electronic Information and Control Engineering, Shandong Institute of Light Industry,Jinan 250100, Shandong, China |
| |
| Abstract: | An improved approximation algorithm about the min-max cycle partition problem is given.This algorithm runs in(O(n~4)) time and its error ratio is at most 3.5 p-2. |
| |
| Keywords: | approximation algorithm hamilton cycle min-max cycle partition |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
