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

NP-COMPLETENESS: 作品数：10被引量：28H指数：2; 导出分析报告; 相关领域：自动化与计算机技术更多>>; 相关作者：谭芳孙世杰刘涛谭芳更多>>; 相关机构：上海大学中国科学院中国民航大学更多>>; 相关期刊：《Control Theory and Technology》《Open Journal of Discrete Mathematics》《上海大学学报（自然科学版）》《Journal of Computer Science & Technology》更多>>; 相关基金：国家自然科学基金教育部长江学者奖励计划国家重点基础研究发展计划更多>>

The Poset Cover Problem: 《Open Journal of Discrete Mathematics》2013年第3期101-111,共11页Lenwood S. Heath Ajit Kumar Nema; 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 of computing, for a poset P, the cardinality of L(P)?is #P-complete. A set {P1,P2,...,Pk}?of poset...; 关键词：LINEAR ORDERS PARTIAL ORDERS NP-COMPLETENESS ALGORITHMS

Application of formal languages in polynomial transformations of instances between NP-complete problems被引量：1: 《Journal of Zhejiang University-Science C(Computers and Electronics)》2013年第8期623-633,共11页Jorge A. RUIZ-VANOYE Joaquín PREZ-ORTEGA Rodolfo A. PAZOS RANGEL Ocotlán DíAZ-PARRA Héctor J. FRAIRE-HUACUJA Juan FRAUSTO-SOLíS Gerardo REYES-SALGADO Laura CRUZ-REYES; We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for ...; 关键词：Formal languages Polynomial transformations NP-COMPLETENESS

SENSOR SELECTION FOR RANDOM FIELD ESTIMATION IN WIRELESS SENSOR NETWORKS被引量：2: 《Journal of Systems Science & Complexity》2012年第1期46-59,共14页Yang WENG Lihua XIE Wendong XIAO; supported by the National Natural Science Foundation of China-Key Program under Grant No. 61032001;the National Natural Science Foundation of China under Grant No.60828006; This paper studies the sensor selection problem for random field estimation in wireless sensor networks. The authors first prove that selecting a set of I sensors that minimize the estimation error under the D-optimal...; 关键词：BLUE covarianee matrix exchange algorithm NP-COMPLETENESS QUANTIZATION random field sensor selection.

The NP-Complete Face of Information-Theoretic Security: 《Computer Technology and Application》2011年第11期893-905,共13页Stefan Rass Peter Schartner; The problem of perfectly secure communication has enjoyed considerable theoretical treatment over the last decades. Results in this area include the identification of multipath transmission as a necessary ingredient, ...; 关键词：Risk management CRYPTOGRAPHY complexity theory NP-COMPLETENESS network security

Sensor selection for parameterized random field estimation in wireless sensor networks: 《控制理论与应用（英文版）》2011年第1期44-50,共7页Weng, Yang Xiao, Wendong Xie, Lihua; supported by the National Natural Science Foundation of China-Key Program (No. 61032001),the National Natural Science Foundation of China (No. 60828006); We consider the random field estimation problem with parametric trend in wireless sensor networks where the field can be described by unknown parameters to be estimated. Due to the limited resources, the network selec...; 关键词：Random field estimation Parametric trend Wireless sensor network Sensor selection NP-COMPLETENESS Distributed processing

宽容交货加权超前延误单机排序问题被引量：3: 《上海大学学报（自然科学版）》2005年第2期149-154,共6页谭芳孙世杰; 该文研究下述宽容交货加权超前延误排序问题:n个工件具有一共同的宽容交货期,任一工件在宽容交货期内完工不受罚,超前或延误则受罚,惩罚系数依赖于工件.排序目标是找一个最优序和最优宽容交货区间位置使最小化加权超前延误惩罚之和.证...; 关键词：排序宽容交货惩罚总和 NP-COMPLETENESS 动态规划

Parameterized Computation and Complexity： A New Approach Dealing with NP-Hardness被引量：21: 《Journal of Computer Science & Technology》2005年第1期18-37,共20页Jian-ErChen; 国家自然科学基金，教育部长江学者奖励计划; The theory of parameterized computation and complexity is a recentlydeveloped subarea in theoretical computer science. The theory is aimed at practically solving alarge number of computational problems that are theore...; 关键词：ALGORITHM computational complexity NP-COMPLETENESS parameterizedcomputation approximation algorithm

A Note on the Single Genotype Resolution Problem: 《Journal of Computer Science & Technology》2004年第2期254-256,F003,共4页HaoLin Ze-FengZhang Qiang-FengZhang Dong-BoBu MingLi; 中国科学院资助项目，国家自然科学基金，国家高技术研究发展计划(863计划)，国家重点基础研究发展计划(973计划)，北京市科委科研项目; This note settles the complexity of the single genotype resolution problemshowing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R.Dondi, and J. Li. The same proof also gives an al...; 关键词：haplotype inference single genotype resolution maximum resolution NP-COMPLETENESS

The Complexity of Checking Consistency of Pedigree Information and Related Problems被引量：1: 《Journal of Computer Science & Technology》2004年第1期42-59,共18页LucaAceto JensA.Hansen AnnaIngdlfsddttir JacobJohnsen JohnKnudsen; Consistency checking is a fundamental computational problem in genetics.Given a pedigree and information on the genotypes (of some) of the individuals in it, the aim ofconsistency checking is to determine whether thes...; 关键词：consistency checking PEDIGREES GENOTYPES NP-COMPLETENESS SATISFIABILITY polynomial time complexity critical genotypes

Renaming a Set of Non-Horn Clauses: 《Journal of Computer Science & Technology》2000年第5期409-415,共7页聂旭民郭青; Several extensions of the logic programming language Prolog to non Horn clauses use case analysis to handle non-Horn clauses. In this paper, analytical and empirical evidences are presented to show that, by making a ...; 关键词：logic for artificial intelligence (AI) automated theorem proving logic programming Horn and non-Horn sets predicate renaming NP-COMPLETENESS

NP-COMPLETENESS