（真）区间图的（多重）染色和问题

论文摘要

(多重)染色和问题在实际生活中有着广泛的应用.染色和问题（SC）就是要找到已知图G的一个点染色,使得所用颜色的总和达到最小。而多重染色和问题（SMC）则是:给定一个图和图中每个点要求要染的颜色种数,要找到一个多重染色使得每个点所染的最大颜色之和达到最小。本文证明了对一类特殊的真区间图(Δ≤（4n）1/4且α（G）≤ω（G）,其中Δ是图G中点的最大次,n是图G的点数,α（G）是G的最大独立点集所包含的点数,ω（G）是G的最大团所包含的点数),MAXIS算法是解决其染色和问题的2-近似算法。并且在本文中我们描述了一种MAXCL算法,从而可以找到任意一个区间图的色和的一个平凡的下界。此外,对于真区间图,本文将LB算法推广到了赋权图的情况,从而找到了一种4-近似算法可以解决其多重染色和问题。

论文目录

摘要

Abstrac

第一章引言

1.1 实际背景

1.2 定义和记号

1.3 相关的结论

1.4 本文的主要结论

第二章真区间图的SC问题的MAXIS算法

2.1 真区间图的MAXIS算法的复杂性

2.2 MAXIS算法是一类特殊真区间图的2-近似算法

第三章用MAXCL算法寻找区间图色和的下界

3.1 用MAXCL算法寻找区间图色和的下界

3.2 MAXCL算法的复杂性

第四章真区间图的SMC问题的一个4-近似算法

4.1 LB算法的推广

4.2 真区间图的SMC问题的一个4-近似算法

结束语

参考文献

致谢

（真）区间图的（多重）染色和问题

论文摘要

论文目录

相关论文文献