论文部分内容阅读
本论文在一维装箱问题、二部图的匹配问题、图的染色问题的基础上研究了新的一个组合最优化问题，即赋权二部图的限制性染色问题。给定赋权二部图G=（X，Y;E;w）及常数L，寻找出E的一个划分，即E=E1∪E2∪…∪Es，这里Ei(i=1，2,…，s)为一个匹配。要求对每一个Ei(i=1，2，…，s)染一种不同的颜色，且权重满足w（Ei）≤L。目标要使得染色数s达到最小。论文证明了该问题是NP-完备的，对此问题论文设计出一个5/2-近似算法，其时间复杂性(O)(|V‖E|3 log|V|)，并设计Matlab程序实现算法。