带限制条件的频率分配的近似算法

摘要

图的频率分配是把频率按顶点所需的数目分配给每个顶点,并且使其满足一定的约束条件.该文在某种约束条件下给出了对六边形图频率分配性能比为(（4k+1）s)/（7kc₂）的算法,其中s=max{c₁,2c₂},c₁,c₂表示inter-site约束.

关键词

频率分配 / 近似算法 / 多重着色

基金资助

国家自然科学基金项目(10571071); 华中师范大学博士研究生科研自主基金项目(2009022)