Quick search algorithm for all Hamiltonian cycles based on k-combination

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (28): 45-47.

• 研究、探讨 • Previous Articles Next Articles

Quick search algorithm for all Hamiltonian cycles based on k-combination

PAN Hexin1，YI Chongxin2，LI Man2

1.Department of Informaition Technology，Changzhou Textile Garment Institute，Changzhou，Jiangsu 213164，China
2.Department of Computer，Shandong Huayu Vocational College，Dezhou，Shandong 253034，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-10-01 Published:2011-10-01

k元组合的Hamiltonan回路快速搜索算法

潘荷新1，伊崇信2，李满2

1.常州纺织服装职业技术学院信息技术系，江苏常州 213164
2.山东华宇职业技术学院计算机系，山东德州 253034

Abstract

Abstract: It presents a novel algorithm increasingly searching all Hamiltonian cycles in a directed or undirected graph and the necessary and sufficient condition for Hamiltonian characteristics based on the definition of k-combination.The algorithm can discover all Hamiltonian cycles，where the basic cycles are not generated.

Key words: k-combination, graph, Hamiltonian cycle

摘要： 通过定义k元组合的方式给出了一个逐步搜索图（有向或元向）的全部Hamiltonan回路的新算法和判定图的哈密顿特性的充要条件。使用该算法可准确地求出Hamiltonan图的全部Hamiltonan回路，不必生成基本回路。

关键词: k元组合, 图, Hamiltonan回路

PAN Hexin1，YI Chongxin2，LI Man2. Quick search algorithm for all Hamiltonian cycles based on k-combination[J]. Computer Engineering and Applications, 2011, 47(28): 45-47.

潘荷新1，伊崇信2，李满2. k元组合的Hamiltonan回路快速搜索算法[J]. 计算机工程与应用, 2011, 47(28): 45-47.

[1]	WU Wenjie, SONG Wen’ai, GAO Xuemei, YANG Jijiang, WANG Qing, HUANG Liping, LEI Yi. Review of X-Ray-Based Computer-Aided Diagnosis of Adult OSA [J]. Computer Engineering and Applications, 2021, 57(9): 1-8.
[2]	JIA Xiang’en, DONG Yihong, ZHU Feng, QIAN Jiangbo. Research Progress of Heterogeneous Graph Convolutional Networks [J]. Computer Engineering and Applications, 2021, 57(9): 36-49.
[3]	LI Jun. Improved Social Force Crowd Evacuation Simulation Model Combined with Shortest Path [J]. Computer Engineering and Applications, 2021, 57(8): 264-270.
[4]	ZHAI Zhengli, LI Penghui, FENG Shu. Research Overview of Adversarial Attacks on Graphs [J]. Computer Engineering and Applications, 2021, 57(7): 14-21.
[5]	ZHENG Kun, KONG Jiangping, ZHOU Jing, CI Kangyi, CHANG Peng. Review of iPPG and Application of Physiological Parameter Detection in Education [J]. Computer Engineering and Applications, 2021, 57(5): 25-35.
[6]	LI Yongzhen, LIAO Husheng. Multi-view Clustering via Graph Convolutional Neural Network [J]. Computer Engineering and Applications, 2021, 57(5): 115-122.
[7]	NI Zongjun, CHEN Hui, ZHANG Yun, SU Min, ZHENG Xiujuan. Non-contact Physiological Parameter Estimation Method Based on Adaptive Denoising [J]. Computer Engineering and Applications, 2021, 57(5): 153-160.
[8]	LIU Teng, CHEN Heng, LI Guanyu. Knowledge Graph Representation Learning Method Jointing FOL Rules [J]. Computer Engineering and Applications, 2021, 57(4): 100-107.
[9]	ZHENG Cheng, DONG Chunyang, HUANG Xiayan. Short Text Classification Method Based on BTM Graph Convolutional Network [J]. Computer Engineering and Applications, 2021, 57(4): 155-160.
[10]	WU Wei, LIU Zeyu. Graph-Based Human-Object Interactions Recognition [J]. Computer Engineering and Applications, 2021, 57(3): 175-181.
[11]	YANG Shanliang, CHANG Zheng. Chinese Implicit Sentiment Analysis Based on Graph Attention Neural Network [J]. Computer Engineering and Applications, 2021, 57(24): 161-167.
[12]	WANG Yulian, LU Mingming. Interpretable Automatic Detection of Android Malware Based on Graph Embedding [J]. Computer Engineering and Applications, 2021, 57(23): 122-128.
[13]	LU Qi, PAN Zhisong, XIE Jun. Bidirectional Attention Question Answering Model Combining Knowledge Representation Learning [J]. Computer Engineering and Applications, 2021, 57(23): 171-177.
[14]	JIANG Yangyang, JIN Bo, ZHANG Baochang. Research Progress of Natural Language Processing Based on Deep Learning [J]. Computer Engineering and Applications, 2021, 57(22): 1-14.
[15]	WU Shuzhao, LI Gongquan, BU Mingwei. Construction of Question Answering System for Suicide Tendency Detection Based on Knowledge Graph [J]. Computer Engineering and Applications, 2021, 57(22): 304-312.

Quick search algorithm for all Hamiltonian cycles based on k-combination

k元组合的Hamiltonan回路快速搜索算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics