单射染色问题的复杂性及其离线与在线算法研究

摘要

无环图G的k顶点单射染色是指k种颜色1，2，...，k，对于图G的各点的一个分配，使得具有公共邻点的两点染以不同的颜色.G的单射色数是使得G为k单射可染的数k的最小值，记为xi(G)。
　　单射染色起源于随机存取机的复杂性理论，可以应用到纠正错误编码的理论中.本文证明了确定一些特殊二部图的单射色数是NP-完全的，并证明了除非NP=ZPP，二部图的单射色数不会有n1/3-∈(∈>0)因子的近似.特别地，树图具有最优的单射染色算法。
　　给定图G=(V，E)和权值函数ω：V→N，C1，C2，...，Ck为G的一个顶点单射k染色，该单射染色的权指的是每个色类中顶点最大权的和，即∑ki=1maxu∈Ciω(u).G的最大单射染色问题是指寻找G的某一单射染色C1，C2，...，Ck，使得它的权∑ki=1maxu∈Ciω(u)最小。
　　本文证明了单射色数有界的幂弦图(power chordal graph)，有多项式时间完成的常因子的最大单射染色近似算法.进一步提出了多项式时间完成的算法MBFF，并证明它对于特殊二部图有常数的近似因子。
　　对于图G，假定它的顶点是随着时间的推移一个接着一个给出的，并且每出现一个点，获得它和之前已出现的所有点在G内的导出子图.图G的在线单射染色算法就是指每出现一个点，该算法立即对其染色，使得有公共邻点的点不能染相同的颜色，并且不更改之前出现的点已染的颜色。
　　本文证明了FF对于P3-free图来说，是一种多项式时间完成的、完美的在线单射染色算法，并得出FF*对于二部图是竞争比为3/2的在线单射染色算法.更进一步提出了多项式时间完成的在线算法BFF，该算法不仅提高了FF*的竞争比，而且是二部图的最优在线算法。

目录

文摘

英文文摘

Contents

前言

第1章 绪论

1.1 基本概念

1.2 图单射染色的历史及已有的结论

第2章 离线单射染色研究

2.1 关于二部图单射染色的NP-完全性

2.2 二部图单射染色的不可近似性

2.3 树的单射染色最优算法

2.4 最大单射染色问题的近似算法

第3章 在线单射染色研究

3.1 P3-free图的在线单射染色

3.2 Triangle-free图与二部图的在线单射染色

第4章 可进一步研究的问题

参考文献

攻读硕士学位期间已完成的论文

致谢