云南高校图书馆联盟文献共享服务平台- NP-完全性

NP-完全性: 作品数：20被引量：36H指数：3; 导出分析报告; 相关领域：理学自动化与计算机技术更多>>; 相关作者：原晋江赵衍才许道云郑永猛禹继国更多>>; 相关机构：郑州大学广州大学上海大学贵州大学更多>>; 相关期刊：《计算机科学与探索》《云南大学学报（自然科学版）》《青岛大学学报（自然科学版）》《重庆通信学院学报》更多>>; 相关基金：国家自然科学基金内蒙古自治区自然科学基金云南省教育厅科学研究基金河南省自然科学基金更多>>

PDD规则下最小化最大延误调度问题: 《运筹学学报》2022年第4期75-86,共12页万龙黄晓莉梅嘉杰; 江西省教育厅科技项目(No.GJJ190250)。; 本文研究机器环境分别为单机、同型机和开放作业机器三种不同环境下的新型调度问题。其中工期根据工件的具体完工时间确定,且连续工期之间的间隔是相等的,一般称这种工期为等间隔工期(PDD)。本文考虑的目标函数都是最小化最大延误。对...; 关键词：调度开放作业等间隔工期延误 NP-完全性

无向路图和块图上的混合控制: 《数学学报（中文版）》2017年第4期641-650,共10页赵衍才单而芳王海超; 国家自然科学基金资助项目(11571222);江苏省自然科学基金(基础研究计划:BK20151117);上海市自然科学基金(14ZR1417900); 图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制...; 关键词：混合控制无向路图块图算法 NP-完全性

一个正则NP-完全问题及其不可近似性被引量：10: 《计算机科学与探索》2013年第8期691-697,共7页许道云王晓峰; 国家自然科学基金No.61262006~~; 通过一个适当的归约变换,可以将一个CNF(conjunctive normal form)公式变换为另一个具有某种特殊结构或性质的公式,使两者具有相同的可满足性。带有正则结构的CNF公式的因子图在图论中具有某些良好的性质和结果,可以用于研究公式的可满...; 关键词：极小不可满足性正则(3 4)-CNF公式 NP-完全性不可近似性

两类广义控制问题的NP-完全性(英文): 《运筹学学报》2012年第3期139-144,共6页赵伟良赵衍才梁作松; supported by the foundation from Department of Education of Zhejiang Province (No.Y201018696);the Nature Science Foundation of Anhui Provincial Education Department(No. KJ2011B090); 研究两类广义控制问题的复杂性:κ-步长控制问题和κ-距离控制问题,证明了κ-步长控制问题在弦图和平面二部图上都是NP-完全的,作为上述结果的推论,给出了κ-距离控制问题在弦图和二部图上NP-完全性的新的证明,并进一步证明了κ-距离控...; 关键词：k-步长控制 k-距离控制 NP-完全性弦图平面二部图

旅行生产线问题: 《云南民族大学学报（自然科学版）》2011年第6期473-475,共3页陈克林; 考虑生产商的最经济的旅行路线问题,把这一问题定义为旅行生产线问题并分析了它的NP-完全性,最后为满足三角不等式的对称网络上的旅行生产线问题设计了一个8-近似算法.; 关键词：旅行生产线问题近似算法 NP-完全性

直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性(英文): 《运筹学学报》2009年第2期41-47,共7页禹继国郑永猛刘桂真张永红; supported by NNSF(10471078) of China;RFDP(20040422004) of Higher Education;Promotional Foundation(2005BS01016) for Excellent Middle-aged or Young Scientists of Shandong Province;UF(XJ0609) and DRF of QFNU; 给定一个简单图G和正整数k,具有完美匹配的图G的k-导出匹配划分是对顶点集V(G)的一个k-划分(V_1,V_2,…,V_k),其中对每一个i(1≤i≤k),由V_i导出的G的子图G[V_i]是1-正则的.k-导出匹配划分问题是指对给定的图G,判定G是否存在一个k-导出...; 关键词：运筹学导出匹配导出匹配划分导出匹配覆盖 NP-完全

限制的星划分问题被引量：1: 《云南大学学报（自然科学版）》2008年第2期109-112,147,共5页张同全李伟东李建平; 国家自然科学研究基金资助项目(10561009);云南省教育厅科学研究基金项目(06J011A); 研究了边赋权图上2类具有权重限制L的最小基数星划分问题-最小基数S(L)划分问题和最小基数S∑(L)划分问题的困难性.得到如下结果:①证明了一般图上最小基数S(L)划分问题的NP-完全性;②证明了一般图上最小基数S∑(L)划分问题的NP-完全性...; 关键词：最小基数 S(L)划分问题 S∑(L)划分问题 NP-完全性近似算法

k-LSAT(k≥3)是NP-完全的(英文)被引量：5: 《软件学报》2008年第3期511-521,共11页许道云邓天炎张庆顺; Supported by the National Natural Science Foundation of China under Grant Nos.10410638, 60310213 (国家自然科学基金); 合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,...; 关键词：线性CNF公式不可满足性 NP-完全性极小不可满足公式归约

对最大团问题的HEWN算法分析: 《河南科学》2006年第5期715-718,共4页郭长庚潘晓伟; 河南省自然科学基金资助项目(0311012100); 对最大团问题的HEWN(hierarchicaledge-weightnetwork)算法进行了复杂性分析.首先通过分析HEWN的结构特点和所需进行的操作,设计了一种实现HEWN算法的数据结构,指出了在HEWN算法中HEWN的存储宜采用邻接多重表和二叉链表相结合的链表表示...; 关键词：算法复杂性 NP-完全性团

网络的分区连接问题被引量：1: 《运筹与管理》2003年第1期28-32,共5页吕红杰杨爱峰; 本文研究了最小支撑树问题的一个变形———分区连接问题 ,即对给定的赋权图及其中若干个顶点 ,求赋权图的权最小支撑森林 ,使得它的每一个分支恰包含唯一的指定顶点。本文给出了该问题的一个时间复杂性为O(|V|2 )的算法。此外 ,还研究...; 关键词：网络优化分区连接多项式算法 NP-完全性

NP-完全性