在本文,我们研究机器环境分别为单机、同型机和开放作业机器三种不同环境下的新型调度问题。其中工期根据工件的具体完工时间确定,......

设G=（V,E）为简单连通图,节点集S（?）V称为G的电力控制集,若V中的所有节点都被S中的节点“控制”.这里节点控制它自己和它所有的邻居,并......

经过几十年的发展,图的控制参数理论已经成为图论中非常活跃的研究领域之一.基于不同的实际背景,人们提出了许多控制参数.控制参数......

NP-completeness理论是计算机算法研究的重要分支之一,该文首先对一个NP-completeness问题--最大团问题的HEWN算法进行研究,设计了......

该文主要研究了几个支撑树上的新优化模型.这些模型可以划分为两类,一类是完全新模型,如多参数最小树模型、Hamming长度的最小树问......

本文研究了最小支撑树问题的一个变形--分区连接问题,即对给定的赋权图及其中若干个顶点,求赋权图的权最小支撑森林,使得它的每一......

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

通过一个适当的归约变换，可以将一个CNF（conjunctive normal form）公式变换为另一个具有某种特殊结构或性质的公式，使两者具有相同的可......

合取范式（conjunctive normal form，简称CNF）公式F是线性公式，如果F中任意两个不同子句至多有一个公共变元．如果F中的任意两个不同子句......

考虑生产商的最经济的旅行路线问题，把这一问题定义为旅行生产线问题并分析了它的NP一完全性，最后为满足三角不等式的对称网络上的旅......

对最大团问题的HEWN（hierarchical edge—weight network）算法进行了复杂性分析．首先通过分析HEWN的结构特点和所需进行的操作，设计了......

研究两类广义控制问题的复杂性：k-步长控制问题和k-距离控制问题，证明了k-步长控制问题在弦图和平面二部图上都是NP-完全的．作为上述......