最大边染色的指数时间算法  

Exponential Time Algorithms for Maximum Edge Coloring

作　　者：凤旺森[1] 张立昂[1] 王捍贫[1] 汤传喜[1] 陈霄[1] 

机构地区：[1]北京大学信息科学技术学院软件研究所高可信软件技术教育部重点实验室,北京100871

出　　处：《计算机研究与发展》2008年第z1期62-66,共5页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2006AA01Z160)

摘　　要：最近,凤旺森,张立昂,曲婉玲,王捍贫对源于无线Mesh网络中的一个新的计算问题——最大边染色问题——提出了常数比近似算法.最大边染色问题要求对图的所有边染色,满足对任一顶点v,与其相关联的所有边所染的颜色种数不超过正整数q(q≥2),求使用颜色种数最多的染色方案.然而,他们并没有给出该问题的任何精确算法.提出了几个指数时间的精确算法并分析了它们的复杂度.对完全图可以在多项式时间内找到精确解.Recently, the authors have proposed constant factor approximation algorithms for a novel computational problem with the name 'maximum edge coloring', which arises from the field of wireless mesh networks. The problem aims to color all the edges in a graph using as many colors as possible, satisfying the constraint: for every vertex in the graph, all the edges incident to it are colored with no more than q(q≥2) different colors. However, they haven't given any accurate algorithm for the problem. In this paper, several exponential time accurate algorithms are proposed for the problem and each one's complexity is analyzed. For complete graphs, accurate solutions are found for them in polynomial time.

关 键 词：最大边染色问题 指数时间算法 回溯 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]