计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2008年
z1期
62-66
,共5页
凤旺森%张立昂%王捍贫%汤传喜%陈霄
鳳旺森%張立昂%王捍貧%湯傳喜%陳霄
봉왕삼%장립앙%왕한빈%탕전희%진소
最大边染色问题%指数时间算法%回溯
最大邊染色問題%指數時間算法%迴溯
최대변염색문제%지수시간산법%회소
最近,凤旺森,张立昂,曲婉玲,王捍贫对源于无线Mesh网络中的一个新的计算问题--最大边染色问题--提出了常数比近似算法.最大边染色问题要求对图的所有边染色,满足对任一顶点v,与其相关联的所有边所染的颜色种数不超过正整数q(q≥2),求使用颜色种数最多的染色方案.然而,他们并没有给出该问题的任何精确算法.提出了几个指数时间的精确算法并分析了它们的复杂度.对完全图可以在多项式时间内找到精确解.
最近,鳳旺森,張立昂,麯婉玲,王捍貧對源于無線Mesh網絡中的一箇新的計算問題--最大邊染色問題--提齣瞭常數比近似算法.最大邊染色問題要求對圖的所有邊染色,滿足對任一頂點v,與其相關聯的所有邊所染的顏色種數不超過正整數q(q≥2),求使用顏色種數最多的染色方案.然而,他們併沒有給齣該問題的任何精確算法.提齣瞭幾箇指數時間的精確算法併分析瞭它們的複雜度.對完全圖可以在多項式時間內找到精確解.
최근,봉왕삼,장립앙,곡완령,왕한빈대원우무선Mesh망락중적일개신적계산문제--최대변염색문제--제출료상수비근사산법.최대변염색문제요구대도적소유변염색,만족대임일정점v,여기상관련적소유변소염적안색충수불초과정정수q(q≥2),구사용안색충수최다적염색방안.연이,타문병몰유급출해문제적임하정학산법.제출료궤개지수시간적정학산법병분석료타문적복잡도.대완전도가이재다항식시간내조도정학해.
