最大边染色的指数时间算法
最近,凤旺森,张立昂,曲婉玲,王捍贫对源于无线Mesh网络中的一个新的计算问题--最大边染色问题--提出了常数比近似算法.最大边染色问题要求对图的所有边染色,满足对任一顶点v,与其相关联的所有边所染的颜色种数不超过正整数q(q≥2),求使用颜色种数最多的染色方案.然而,他们并没有给出该问题的任何精确算法.提出了几个指数时间的精确算法并分析了它们的复杂度.对完全图可以在多项式时间内找到精确解.
最大边染色 指数时间算法 完全图 复杂度 精确解
凤旺森 张立昂 王捍贫 汤传喜 陈霄
北京大学信息科学技术学院软件研究所高可信软件技术教育部重点实验室,北京,100871
国内会议
南宁
中文
62-66
2007-11-01（万方平台首次上网日期，不代表论文的发表时间）