(真)区间图的(多重)染色和问题

来源 :华中师范大学 | 被引量 : 0次 | 上传用户:tdwh14226
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
(多重)染色和问题在实际生活中有着广泛的应用.染色和问题(SC)就是要找到已知图G的一个点染色,使得所用颜色的总和达到最小.而多重染色和问题(SMC)则是:给定一个图和图中每个点要求要染的颜色种数,要找到一个多重染色使得每个点所染的最大颜色之和达到最小.本文证明了对一类特殊的真区间图(△≤4 4n且α(G)≤ω(G),其中△是图G中点的最大次,n是图G的点数,α(G)是G的最大独立点集所包含的点数,ω(G)是G的最大团所包含的点数),MAXIS算法是解决其染色和问题的2-近似算法.并且在本文中我们描述了一种MAXCL算法,从而可以找到任意一个区间图的色和的一个平凡的下界.此外,对于真区间图,本文将LB算法推广到了赋权图的情况,从而找到了一种4-近似算法可以解决其多重染色和问题.
其他文献
本文根据三维水平井井眼轨道设计的实际背景,把工程中的干扰因素考虑成随机过程,以井斜角、方位角、北坐标、东坐标和垂深坐标为状态变量,以装置角、曲率半径、弧长为控制变
高振荡函数的积分问题在电磁计算,量子力学,信号处理等实际应用中是一个核心的研究方向,问题的关键就是如何给出高振荡函数积分的高效数值算法。因为用Gauss、Newton-Cotes等传
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
本文主要研究广义模糊积分的收敛理论以及广义模糊可积函数(列)的某些性质。主要工作如下: (1)给出了广义三角模的一个减弱了的定义。提出并研究了广义三角模的两个条件(S-
本文首先通过定义新的蕴涵算子→T,建立一个新的直觉模糊命题逻辑系统(I02,(),v,→T),讨论此蕴涵算子的性质,研究系统I02上的广义拟重言式,它共分为五种不同的广义拟重言式:(1/2,1/2)-
本文研究一类特殊的非标准型逆热传导问题,即如下的含有对流项ux的抛物方程侧边值问题:我们要利用x=1处的温度数据g(t)来确定区间[0,1)上的温度分布u(x,t).这是一类严重的不适定
对Gross-Pitaevskii方程运用了Painlevé分析的方法,得到了该方程在Painlevé可积意义下的必要条件,并找到变换,将该方程得变换形式化为标准的非线性Schrodinger方程,从而说
非局部问题有着广泛的来源和重要的研究意义.在引言中我们将简单介绍非局部问题的来源和研究现状,并且将介绍实际背景和研究方法以及本文主要研究的问题:非局部边界下的椭圆型
省委书记、省人大主任田成平最近在同公选副厅级领导干部岗位培训班学员座谈时指出,中青年领导干部的成长是有一定规律的。一是知识武装,二是实践锻炼。知识武装,主要包括基
时间序列分析技术是研究股票市场的一个非常重要的工具。本文对金融时间序列分析的技术进行了探讨,不仅介绍了传统的时间序列模型,而且还引入了一种新的模型——all-pass模型