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

NP-COMPLETE: 作品数：38被引量：101H指数：5; 导出分析报告; 相关领域：自动化与计算机技术更多>>; 相关作者：周灵孙亚民郭伟席裕庚伍之昂更多>>; 相关机构：国防科学技术大学南京理工大学上海交通大学南京财经大学更多>>; 相关期刊：《Progress in Natural Science:Materials International》《Open Journal of Discrete Mathematics》《Science China(Information Sciences)》《Journal of Systems Engineering and Electronics》更多>>; 相关基金：国家自然科学基金国家重点基础研究发展计划国家高技术研究发展计划贵州省省长专项基金项目更多>>

Probe Machine Based Computing Model for Maximum Clique Problem: 《Chinese Journal of Electronics》2022年第2期304-312,共9页CUI Jianzhong YIN Zhixiang TANG Zhen YANG Jing; supported by the National Natural Science Foundation ty(KJ2019A0538)of China(62072296,61702008);Natural Science Foundation of Anhui University(KJ2019A0538)。; Probe machine(PM)is a recently reported mathematic model with massive parallelism.Herein,we presented searching the maximum clique of an undirected graph with six vertices.We constructed data library containing n subl...; 关键词：Probe machine NP-COMPLETE Maximum clique problem

Parallel-batch scheduling with deterioration and rejection on a single machine被引量：3: 《Applied Mathematics(A Journal of Chinese Universities)》2020年第2期141-156,共16页LI Da-wei LU Xi-wen; Supported by the National Natural Science Foundation of China(11871213,71431004).; The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the mach...; 关键词：parallel-batch scheduling REJECTION DETERIORATION FPTAS NP-COMPLETE

Fast Algorithm for the Travelling Salesman Problem and the Proof of P = NP被引量：1: 《Applied Mathematics》2018年第12期1351-1359,共9页Jinliang Wang; In the theory of computational complexity, the travelling salesman problem is a typical one in the NP class. With the aid of a brand-new approach named “maximum-deleting method”, a fast algorithm is constructed for ...; 关键词：TRAVELLING SALESMAN PROBLEM P versus NP PROBLEM NP-COMPLETE Computational Complexity Maximum-Deleting Method

Some NP-Complete Results on Signed Mixed Domination Problem: 《Journal of Mathematical Research with Applications》2017年第2期163-168,共6页Yancai ZHAO Huahui SHANG H.Abdollahzadeh AHANGAR N.Jafari RAD; Supported by the Natural Science Foundation of Jiangsu Province(Grant No.BK20151117);the Key Scientific Research Foundation of Higher Education Institutions of Henan Province(Grant No.15B110009); Let G =（V, E） be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x...; 关键词：ksigned mixed dominating function signed mixed domination number NPcompleteness

Solving the Binary Linear Programming Model in Polynomial Time: 《American Journal of Operations Research》2016年第1期1-7,共7页Elias Munapo; The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex q...; 关键词：NP-COMPLETE Binary Linear Programming Convex Function Convex Quadratic Programming Problem Interior Point Algorithm and Polynomial Time

On the parameterized vertex cover problem for graphs with perfect matching被引量：2: 《Science China(Information Sciences)》2014年第7期101-112,共12页WANG JianXin LI WenJun LI ShaoHua CHEN JianEr; supported by National Natural Science Foundation of China(Grant Nos.61232001,61173051,61128006,71221061);Hunan Provincial Innovation Foundation For Postgraduate(Grant No.CX2011B088); A vertex cover of an n-vertex graph with perfect matching contains at least n/2 vertices.In this paper,we study the parameterized complexity of the problem vc-pm^＊that decides if a given graph with perfect matching h...; 关键词：NP-COMPLETE parameterized algorithm vertex cover iterative compression

Solving a Traveling Salesman Problem with a Flower Structure: 《Journal of Applied Mathematics and Physics》2014年第7期718-722,共5页Gabriele Martino; This works aims to give an answer to the problem P = NP? The result is positive with the criteria that solve the Traveling Salesman Problem in polynomial cost of the input size and a proof is given. This problem gets ...; 关键词：TRAVELING SALESMAN Problem POLYHEDRON FLOWER NP-COMPLETE

A Non-Conventional Coloring of the Edges of a Graph: 《Open Journal of Discrete Mathematics》2012年第4期119-124,共6页Sándor Szabó; Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we ...; 关键词：Maximum CLIQUE COLORING the VERTICES of a GRAPH COLORING the EDGES of GRAPH NP-COMPLETE Problems

Applying Surface-Based DNA Computing for Solving the Dominating Set Problem: 《American Journal of Molecular Biology》2012年第3期286-290,共5页Hassan Taghipour Mahdi Rezaei Heydar Ali Esmaili; The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set proble...; 关键词：Parallel Computing Surface-Based DNA Computers Dominating Set PROBLEM NP-COMPLETE PROBLEM

A Variant of Multi-task n-vehicle Exploration Problem: Maximizing Every Processor's Average Profit被引量：1: 《Acta Mathematicae Applicatae Sinica》2012年第3期463-474,共12页Yang-yang XU Jin-chuan CUI; Supported by Daqing oilfield company Project of PetroCHINA under Grant (dqc-2010-xdgl-ky-002);Key Laboratory of Management, Decision and Information Systems, Chinese Academy of Sciences;Beijing Research Center of Urban System Engineering; We discuss a variant of the multi-task n-vehicle exploration problem. Instead of requiring an optimal permutation of vehicles in every group, the new problem requires all vehicles in a group to arrive at the same dest...; 关键词：multi-task n-vehicle exploration problem （MTNVEP） maximizing average profit （MAP） fractional partition （FP） NP-COMPLETE strongly NP-complete

NP-COMPLETE