限制的星划分问题

来源 :云南大学学报：自然科学版 | 被引量 : 0次 | 上传用户：wanghua035871

【摘要】

：

研究了边赋权图上2类具有权重限制L的最小基数星划分问题-最小基数S（L）划分问题和最小基数S∑（L）划分问题的困难性.得到如下结果：①证明了一般图上最小基数S（L）划分问题的NP-完全性;

【作者】

：

张同全李伟东李建平

【机构】

：

云南大学物理科学技术学院非线性中心,云南大学数学与统计学院数学系

【出处】

：

云南大学学报：自然科学版

【发表日期】

：

2008年2期

【关键词】

：

最小基数 S(L)划分问题 S∑(L)划分问题 NP-完全性近似算法 minamal cardinality S（L） partition problem S

【基金项目】

：

国家自然科学研究基金资助项目（10561009）,云南省教育厅科学研究基金项目（06J011A）.

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

研究了边赋权图上2类具有权重限制L的最小基数星划分问题-最小基数S（L）划分问题和最小基数S∑（L）划分问题的困难性.得到如下结果：①证明了一般图上最小基数S（L）划分问题的NP-完全性;②证明了一般图上最小基数S∑（L）划分问题的NP-完全性,并证明了对于任意小的正数ε,一般图上的最小基数S∑（L）划分问题不存在（3/2-ε）-近似算法,除非P=NP.

其他文献

剩余类环上的置换多项式

研究了一类典型的多元奇异多项式，得到了其为置换多项式的充要条件，推广了张起帆的结果．此外，得到了多项式为模3^ω的置换多项式的充要条件，从而发展了Revest的结果．

期刊

置换多项式正交组剩余类环permutation polynomial orthogonal system residue class ring

带粗糙核的分数次积分算子交换子在Morrey-Herz空间的加权有界性

受Morrey-Herz空间和奇异积分算子的启发,讨论了加权Morrey-Herz空间MKαp,,qλ（ω1,ω2）上的算子.基于Ap权函数理论,应用调和分析的方法,得到了带粗糙核的分数次积分算子交换

期刊

MORREY-HERZ空间交换子权有界性Morrey-Herz space commutator weighted boundedness

关于拓扑空间上的几乎不动点定理和不动点定理

定义拓扑空间的R-子集的概念,利用古典的KKM原理的开[闭]形式得到一般拓扑空间上的KKM型定理并建立连续选择定理,然后给出局部一致空间上的上[下]半连续映射的几乎不动点定理

期刊

上[下]半连续W-R-KKM映射局部一致空间几乎不动点性质R-子集C-R-子集几乎R-子集upper[lower]semicontinuous

求解Benjamin—Bona—Mahony方程的拟紧致差分格式

对Benjamin—Bona—Mahony（BBM）方程的初边值问题进行了数值研究，提出了一个3层拟紧致隐式差分格式，讨论了差分解的存在唯一性，并利用离散泛函分析方法分析了该格式的二阶收敛性与

期刊

BBM方程有限差分格式收敛性稳定性Benjamin - Bona - Mahony equation finite difference schem

Littlewood-Paley算子及其交换子的有界性

运用Herz型Hardy空间的原子和分子分解理论,对Littlewood-Paley算子及其交换子进行了讨论,证明了Littlewood-Paley算子gψ及其与BMO函数生成的交换子gψ,b在Herz型Hardy空间

期刊

LITTLEWOOD-PALEY算子交换子HERZ型HARDY空间有界性Littlewood-Paley operator commutator H

左端简单支撑右端被滑动夹子夹住的奇异梁方程的正解

利用积分方程技巧和锥上的Guo—Krasnosel＇skii不动点定理研究了一类非线性四阶两点边值问题的正解存在性，其中允许非线性项，（t，u，v）在t=0，t=1及u=0，v=0处奇异．在力学上这类问题模拟了

期刊

奇异常微分方程边值问题正解存在性singular ordinary differential equation boundary value pro

Hilbert空间中非扩张映像族公共不动点的存在性

在Hilbert空间中,首先利用距离投影算子技巧证明了由Aoyama,Kohsaka和Takahashi构造的关于非扩张映像族的收缩投影方法所生成的序列是有意义的;其次获得了非扩张映像族有公共

期刊

非扩张映像族公共不动点存在性收缩投影方法family of nonexpansive mappings common fixed points ex

几种不同类型烟叶非挥发性有机酸的比较分析

测定了烤烟、香料烟、白肋烟和马里兰烟等不同类型烟叶中非挥发性有机酸的含量,用统计方法比较了几类烟叶之间草酸、苹果酸、柠檬酸和总酸量之间的差异.草酸:马里兰烟含量最

期刊

烤烟香料烟白肋烟马里兰烟非挥发性有机酸比较flue-cured tobaccoorient tobaccoburley tobaccoMary

多队列双服务器同步控制策略轮询系统负载均衡性能研究

在分析目前因特网架构特点、新业务需求、Web服务负载瓶颈、服务解决方案及其未来发展趋势的基础上,提出了多队列双服务器轮询机制下的系统负载均衡结构.进一步利用轮询多址

期刊

负载平衡多队列双服务器轮询系统同步调度策略WEB服务器load balancemultiqueue double servers pollingsy

基于遗传算法的分形曲面插值拟合

分形插值作为重要的数学模型,已经在有分形特征的地理地形,材料表面等领域.本文首先阐述了分形插值的方法,然后结合遗传算法的搜索优化的特点,来选择纵向压缩因子的最优值.实

期刊

分形曲面曲面插值拟合遗传算法fractal surfacesurface interpolation fittinggenetic algorithm

限制的星划分问题

与本文相关的学术论文