论文部分内容阅读
本文主要研究了顶点着色二部图中包含颜色最多的独立集问题（Maximum Colorful Independent Set Problem,MCISP）。这一问题可描述如下,对于任意给定的顶点着色二部图,顶点中颜色的着色方式并无限制,在该图中找含颜色数最多的独立集。一般的MCISP问题在二部图上是NP-hard的,本文针对这一NP-hard问题,设计了近似算法,并对每种颜色出现次数有限制的情况,证明了问题是NP-hard且设计了两个多项式时间的近似算法,论文的各个章节具体内容如下。第一章,主要介绍了图论基本概念和计算复杂性的定义,并对近似算法、布尔可满足性问题、顶点着色图与独立集问题进行了阐述。第二章,利用二部图中独立集的性质,论文设计了求解一般二部图上颜色数最多的独立集问题中最坏情况界是2的近似算法,并针对完全二部图块中顶点的每种颜色恰出现3次时这一特殊的NP-hard情形,运用了贪婪思想,给出了最坏情况界为34的近似算法。第三章,首先利用均衡MAX-（3,B2）-SAT和MAX-2SAT证明了无爪图（claw-free graph）,无P6路的图（P6-free graph）和无叉图（fork-free graph）上MCISP问题是NP-hard的,从而说明了当颜色恰出现2次时的完全二部图块上的MCISP问题仍然是NP-hard,故研究了这一情形下的近似算法。接着运用贪婪思想给出最坏情况界为23的算法,然后对这一算法进行改进,提出了最坏情况界为34的近似算法。第四章对全文的内容进行了总结并对接下来的研究方向给出了分析和展望。