NP-completeness相关论文
,Application of formal languages in polynomial transformations of instances between NP-complete prob
...
本文考虑了下述宽容交货加权超前延误的单机排序问题：有n个工件需在同一台机器上加工，各工件有一共同的宽容交货期，宽容交货期的大小......
Consistency checking is a fundamental computational problem in genetics. Given a pedigree and information on the genoty......
为探究吕家坨井田地质构造格局,根据钻孔勘探资料,采用分形理论和趋势面分析方法,研究了井田7......
This paper studies the sensor selection problem for random field estimation in wireless sensor networks.The authors firs......
Consistency checking is a fundamental computational problem in genetics. Given a pedigree and information on the genoty......
The theory of parameterized computation and complexity is a recently developed subarea in theoretical computer science. ......
讨论了分批排序中工件具有带学习效应、目标函数为极小化加权总完工时间两个问题,分别就所有工件的加工时间都相等的情况给出了两......
最优技能集扩张问题是从一个已有技能集扩张为一个要求技能集,使得扩张过程的获取费用为最小.目前文献中已有基于整数规划的数值方......
研究了一维装箱问题 (BinPackingProblem) ,给出了一个新的近似算法 :交叉装填算法 (简称CF算法 ) .证明了CF算法达到装箱问题的最......
考虑一个有两个功能部件的机器模型,每个部件要么是有序的,要么类似于管道并列的.关于这类机器模型的3个NP-完成结果在[1]中有所阐......
本文介绍了一种UET系统中有效的调度算法,其时间复杂性函数为O(na(n)+e)。该算法对m=2台处理机的调度为最优,而对m≥3台处理机上的......
合取范式(CNF)公式H到F的同态是一个从H的文字集合到F的文字集合的映射、并保持补运算和子句映到子句.同态映射保持一个公式的不可......
对最大团问题的HEWN（hierarchical edge-weight network）算法进行复杂性分析。首先通过分析HEWN的结构特点和所需进行的操作，设计了一......
对于许多网络应用而言,精确的网络链路实际使用带宽的监测非常重要.首先,为了减少监测过程对实际网络带宽的影响提出一个网络链路......
在基于Petri网的模型验证方法中，步被广泛用于减少变迁实施产生的语义交织．为了研究基于步的构造算法的计算复杂性，提出步的判定问题，......
该文研究下述宽容交货加权超前延误排序问题:n个工件具有一共同的宽容交货期,任一工件在宽容交货期内完工不受罚,超前或延误则受罚......
介绍了OSPF协议中最重要的两个部分-寻径和L-S信息广播处理，并且对他们的算法及复杂性作出了分析，在分析的基础上，将L-S信息广播处理......
Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立.我们首先用一个反例指出Bhatia等对Xu等的NP-完全性......
本文给出了表的等价性判定的一些结果：三元可满足性问题，表达式的ＮＰ完全性，表的ＮＰ完全性，还给出了函数依赖对表的影响，强等价性的复杂性的一......
A partial order or poset P=(X, on a (finite) base set X?determines the set L(P)?of linear extensions of P. The problem o......
约束满足问题(CSPs)在数据库检索(Database Retrieval)、集成电路设计、计算机视觉、定理证明、机器人规划、机器学习等诸多研究领......
本文根据运输问题中一类常见的情况建立了在并容量网络中求最大并流的网络模型，证明了最大并流问题的ＮＰ完全性，并给出了求解该问题的一......
