论文摘要
(多重)染色和问题在实际生活中有着广泛的应用.染色和问题（SC）就是要找到已知图G的一个点染色,使得所用颜色的总和达到最小。而多重染色和问题（SMC）则是:给定一个图和图中每个点要求要染的颜色种数,要找到一个多重染色使得每个点所染的最大颜色之和达到最小。本文证明了对一类特殊的真区间图(Δ≤（4n）1/4且α（G）≤ω（G）,其中Δ是图G中点的最大次,n是图G的点数,α（G）是G的最大独立点集所包含的点数,ω（G）是G的最大团所包含的点数),MAXIS算法是解决其染色和问题的2-近似算法。并且在本文中我们描述了一种MAXCL算法,从而可以找到任意一个区间图的色和的一个平凡的下界。此外,对于真区间图,本文将LB算法推广到了赋权图的情况,从而找到了一种4-近似算法可以解决其多重染色和问题。
论文目录
相关论文文献
- [1].特殊图的图修正问题研究综述[J]. 计算机科学 2018(03)
- [2].区间图中边的类型[J]. 现代妇女(下旬) 2014(01)
- [3].求解区间图上的罗马控制数的动态规划算法[J]. 计算机应用研究 2018(07)
- [4].随机飘移下变抽样区间图的设计[J]. 系统管理学报 2010(01)
- [5].毛虫树的扩充侧廓[J]. 天中学刊 2008(05)
- [6].求解区间图K-连接最短路径问题的在线算法[J]. 计算机工程 2012(11)
- [7].无爪图上团横贯数的界[J]. 运筹学学报 2013(02)
- [8].分裂图的区间图完全化问题（英文）[J]. 数学季刊(英文版) 2015(02)
- [9].完全多部图的区间图完全化问题(英文)[J]. 数学季刊 2009(02)
- [10].树的线图的图扩充问题[J]. 数学的实践与认识 2009(16)
- [11].k-路的零度[J]. 滁州学院学报 2013(02)
- [12].图同构判定的新方法[J]. 河北理工大学学报(自然科学版) 2008(01)
- [13].可变抽样区间图[J]. 杭州师范大学学报(自然科学版) 2009(01)
- [14].复合式双层地基极限承载能力分析[J]. 内蒙古水利 2013(01)
- [15].树的补图的区间图完全化问题(英文)[J]. 应用数学 2009(01)
- [16].一种计算Ad hoc网络K-终端可靠性的线性时间算法[J]. 电子工程师 2008(02)