基于SAT问题的独立集算法  

An Independent Set Algorithm for SAT Problems

作　　者：李勤丰[1] 

机构地区：[1]金陵科技学院基础部,江苏南京211169

出　　处：《金陵科技学院学报》2010年第2期6-9,共4页Journal of Jinling Institute of Technology

摘　　要：独立集问题是组合优化中典型的NP问题,近年来解决SAT问题的算法层出不穷。利用粘贴模型将独立集问题转化为SAT问题,进而解决原问题,并用实例说明了该方法的可行性。The independent set problem is a typical NP-complete problem in combinatorial optimization. There are many ways to solve SAT problems. The sticker model is used to convert the independent set problem to the SAT so as to settle the original problem. It has been proved to be a feasible method.

关 键 词：SAT DNA计算 粘贴模型 独立集 

分 类 号：O157.6[理学—数学] TP301[理学—基础数学]