【摘 要】
：
在本文中，主要研究了赋权区间图上限制性的染色问题．赋权区间图上限制性的染色问题是指：对于一个赋权的区间图G=(V,E;ω)和一个正整数B，对区间图进行染色，要求在数轴上相交的区间
论文部分内容阅读
在本文中，主要研究了赋权区间图上限制性的染色问题．赋权区间图上限制性的染色问题是指：对于一个赋权的区间图G=(V,E;ω)和一个正整数B，对区间图进行染色，要求在数轴上相交的区间不能染同一颜色，并且每种颜色所染区间的权重之和不超过给定的正整数B，使得染色数达到最小．同时还把染色装箱问题转化为赋权区间图上限制性的染色问题的一种特殊情形进行了研究．染色装箱问题是指:任意给定一个物品集合L={α1,α2…,αn}和一个颜色集合R={r1，r2…,rk}，每个物品的大小为叫ω(αi)∈(0,1]，i=1,2…,n，同时每个物品有一个颜色rji∈R.要求将所有物品全部放入容量为1的箱子中，并且同一颜色的物品不能放在同一个箱子里，使得用去的箱子数达到最小．得到了如下结果：(1)赋权区间图上限制性的染色问题是强NP-难的，不存在近似值为3/2-ε的多项式算法，这里ε>0，并设计出两个启发式算法；(2)当k=2时，染色装箱问题可在多项式时间内求得最优解；当k≥3时，该问题是APX-难的，并给出一个2-近似算法．
第一章：回顾了问题的由来，给出了最近的一些相关研究成果．
第二章：给出了文中所出现的定义、概念和符号．
第三章；对赋权区间图上限制性的染色问题的困难性进行分析，并给出一些算法．
第四章：对染色装箱问题的困难性进行分析，并给出一些算法．
最后，给出了相关结论以及未来的研究方向．
其他文献
大学生网络安全危机表现为网络受骗频发、网络道德缺失、网络言行失范、网络安全意识欠缺.其成因包括:高校大学生网络法治观念淡薄、高校网络安全教育制度设计缺失、高校网络
基于SVG技术构建的CAD图形管理系统，可用于将二维CAD图形进行网络发布，让用户可以上传、下载、查找、浏览CAD图形以及获取其内部图元信息。 获取DXF格式文件中的图元数据信
生物膜的形变过程是一个非常重要的问题，人们在这个领域取得了很多有意义的成果。柱状生物膜的形变可以通其准线的变化来描述。本文中，针对柱状膜的指向模型和退化模型，设计了时
仿射球是仿射微分几何里最重要的研究对象之一，其中完备仿射球的分类结果是由W.Blaschke，E.Calabi，S.T.Yau，S.Y.Cheng等完成.特别S.T.Yau和S.Y.Cheng对于E.Calabi猜测即关于完备
本文主要在模空间的框架下研究色散方程.色散方程的研究有着漫长历史和丰富的理论体系，因为一致分解在改进色散估计所起的作用，近几年来，人们开始在模空间框架下研究色散方程.其
当前,国家正大力推进电子商务进农村,其目的之一就是把农村特色农产品推向更为广阔的市场,实现农民的增收.如何实现农产品的附加值最大化,这其中蕴藏着巨大的商机,给大学生创
本文研究了对数正态分布下伴有随机移走的逐级删失定时截尾恒加寿命试验模型的抽样设计。我们事先假定被随机移走的试验产品数是服从二项分布的，其中每一个试验产品被随机移走
本论文研究了装箱问题的一个衍生问题：染色装箱问题，即在装箱问题中。给每个物品指定一个颜色，要求每个箱子中所装的物品颜色各不相同，使得所需要的箱子数目尽可能少。该问题是一
本文研究了一类投连寿险产品的定价方法，这类产品具有以下特点：将低端收益设定为公司违约时的给付，中端收益设定为最低保证价值，以及高端收益设定为在公司价值较高时最低保证价值