缩减MAX SAT问题中变元个数的多项式时间算法

针对ＭＡＸ ＳＡＴ问题，提出一个缩减变元个数的多项式时间算法，若Ｔ是ＭＡＸ ＳＡＴ问题的任何一个实例，该处法将其转化为另一个实例Ｐ，具Ｐ中的变元个数小于Ｔ中的子句个数，在采用其他算法求出Ｐ的最优解后，可用Ｐ的最优解构造Ｔ的最优解。此算法可作为一个有效的预处理处理。     

河布线中的间隔问题及其算法设计

本文讨论了间距不等情况下的河布线(Rivef Routing)中的间隔问题(separationproblem),且给出了一个O(n)时间算法。     

一类L—Fuzzy集的逻辑结构

设L={0,α,β,1}为链或布尔格,L~n中L—模糊集由(?)L(L~n)=={μ|μ~2L~n→L}定义的。本文主要结果为: (1)对μ∈(?)L(L~n),μ可写成如下形式μ=μ~0·0 μ~1·1 μ~2·α μ~3·β=sum from j=0 to 4n-1 α_jm_j其中,α_j∈{0,α,β,1} m_j=multiply from i=1 to n X_i~(ji) (X_i~(ji)为X_i逻辑分量) (2){X|μ(x)=α_i}=sum from pi to m_i (3)L~n中L—模糊集的α—水平集为N_μ(α_i)={X|μ(X)≥α_i,X∈L~n)N_μ(α_i)具有如下性质: 1°、当α_1≥α_2时,N_μ(α_1)相似文献   

逻辑网络复盖弧的通路计数问题

本文对组合逻辑网络故障诊断算法复杂性评估涉及的问题:在组合逻辑网络中(1)自初级输入顶点到初级输出顶点共有多少条单通路;(2)提出一个复杂性为O(n~2·m)的算法能找出自初级输入顶点到初级输出顶点有(m-|V_1| 1)条单通路复盖其所有弧;(3)其中最少存在多少条这样的单通路能复盖该逻辑网络的所有弧。应用图论方法分别给予回答和论证。     

关系网的代数规范说明

将关系网看作一个抽象数据类型,给出了其代数规范说明.这个关系网是它的代数规范说明的一个代数,代数规范说明的任一代数是一个关系网;讨论了关系网在同态下的性质,以及代数规范说明的代数与关系网模式和位置/变迁网的关系。     

弦图上团划分数问题的复杂性

本文得到下述结果:(1)在无K_4图上或在弦图上,求团划分数问题是NP——困难的;(2)找到在无K_4弦图上求团划分数的线性算法和在弦图上求团覆盖数的线性算法。