一个高效的3SAT到Hamilton环转化方法

杜立智; 张晓龙

首页> 中文期刊> 《南京理工大学学报：自然科学版》 >一个高效的3SAT到Hamilton环转化方法

一个高效的3SAT到Hamilton环转化方法

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

为了得到将三元可满足性问题(3-Satisfiability problem,3SAT)直接转化为哈密尔顿环(Hamilton cycle)的高效转化方法,该文以长年对哈密尔顿环研究计算所探索出的规律为基础进行研究。通过对各种可能实现转化的图形组合进行全面的比较分析,得出用无向图的两个节点模拟3SAT的一个变量,用无向图的13个节点模拟3SAT的一个子式的方法,实现了3SAT到哈密尔顿环的高效转化。研究结果表明:该转化所需要的节点数及其边数是最优的。

著录项

来源
《南京理工大学学报：自然科学版》 |2013年第4期|506-510|共5页
作者
杜立智; 张晓龙;
展开▼
作者单位

武汉科技大学计算机科学与技术学院;

展开▼
原文格式 PDF
正文语种 chi
中图分类算法理论;
关键词
计算机算法; 哈密尔顿环; 三元可满足性问题; 非确定性多项式时间完全;

相似文献

中文文献
外文文献
专利

1. 一个关于Hamilton环(路)的多项式时间算法 [J] . 杜立智 . 电脑与信息技术 . 2010,第001期
2. 有向线图存在Hamilton圈和Hamilton路的一个充要条件 [J] . 王瑞霞 . 太原科技大学学报 . 2007,第005期
3. 从无穷维可积Hamilton系统到有限维可积Hamilton系统的一个一般途径 [J] . 曾云波 ,李翊神 . 数学进展 . 1995,第002期
4. 具幂零鞍点的Hamilton系统的周期环域的环性 [J] . LI Huimin ,ZHANG Erli . 四川师范大学学报（自然科学版） . 2019,第005期
5. 稻壳灰负载FeCl2·2H2O:一个温和高效的多相催化剂用于Friedlnder杂成环反应合成多取代喹啉(英文) [J] . Farhad Shirini ,Somayeh Akbari-Dadamahaleh ,Ali Mohammad‐Khah . 催化学报 . 2013,第12期
6. 关于Ｈａｍｉｌｔｏｎ系统周期轨道的一个注记 [C] . 许克峰 . 第六届全国非线性振动会议 . 1992
7. Hamilton ODEs的高效辛算法和Hamilton PDEs的多辛算法 [A] . 刘宏宇 . 2004

一个高效的3SAT到Hamilton环转化方法

摘要

著录项

相似文献

相关主题

期刊订阅