Lower bounds for Ramsey numbers based on simulated annealing algorithm

doi:10.3778/j.issn.1002-8331.2009.07.022

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (7): 70-71.DOI: 10.3778/j.issn.1002-8331.2009.07.022

• 研究、探讨 • Previous Articles Next Articles

Lower bounds for Ramsey numbers based on simulated annealing algorithm

SHAO Ze-hui¹,WANG Zi-cheng¹,XIAO Jian-hua²

1.Department of Control Science and Engineering，Huazhong University of Science and Technology，Wuhan 430074，China
2.Research Center of Logistics，Nankai University，Tianjin 300071，China

Received:2008-12-02 Revised:2009-01-19 Online:2009-03-01 Published:2009-03-01
Contact: SHAO Ze-hui

求解Ramsey数下界的模拟退火算法

邵泽辉¹,王子成¹,肖建华²

1.华中科技大学控制科学与工程系，武汉 430074
2.南开大学现代物流研究中心，天津 300071

通讯作者: 邵泽辉

Abstract

Abstract: For given graphs G₁，G₂，the 2-color Ramsey number R（G₁、G₂） is defined to be the least positive integer p such that every 2-coloring of the edges of complete graph K_p contains a monochromatic copy of G_i colored with i，for 1≤i≤2.With the help of simulated annealing algorithm，some lower bounds of Ramsey numbers for the families R（W_m，K_n），R（B_m，K_n），R（F_m，K_n） is obtained.

Key words: Ramsey number, simulated annealing, edge coloring, cyclic graph

摘要： 对于图G₁、G₂，2色广义Ramsey数R（G₁，G₂）是指最小正整数p，使得每一个p阶的图G，或者G包含G₁，或者G的补图包含G₂。用改进的模拟退火算法求解得到了R（W_m，K_n），R（B_m，K_n），R（F_m，K_n），类型的一些Ramsey数的下界。

关键词: Ramsey数, 模拟退火, 边着色, 循环图

SHAO Ze-hui¹,WANG Zi-cheng¹,XIAO Jian-hua². Lower bounds for Ramsey numbers based on simulated annealing algorithm[J]. Computer Engineering and Applications, 2009, 45(7): 70-71.

邵泽辉¹,王子成¹,肖建华². 求解Ramsey数下界的模拟退火算法[J]. 计算机工程与应用, 2009, 45(7): 70-71.

[1]	MA Yanfang, LI Baoyu, YANG Yifu, FENG Cuiying. Two-Echelon Capacitated Vehicle Routing Model and Algorithm for Fresh Products Distribution with Customer Classification [J]. Computer Engineering and Applications, 2021, 57(20): 287-298.
[2]	TONG Wenlin, CHEN Dewang, HUANG Yunhu, LYU Yisheng. Fuzzy System Optimization Method Based on Simulated Annealing and Rule Reduction [J]. Computer Engineering and Applications, 2021, 57(16): 142-150.
[3]	ZHANG Kai, JIN Peng, CUI Yong. Multi-vehicle Split Pickup and Delivery Problem with Time Windows [J]. Computer Engineering and Applications, 2021, 57(14): 281-288.
[4]	YU Zhong, GU Renbin, FAN Jiulun. Research on Channel Access Method of LoRaWAN Based on LBT-SA [J]. Computer Engineering and Applications, 2020, 56(24): 95-101.
[5]	LI Yan, ZHANG Xin. Equitable Edge Coloring of Outer-1-Planar Graphs [J]. Computer Engineering and Applications, 2019, 55(24): 37-40.
[6]	ZHU Yongchao, ZHOU Chuan, GUO Jian, WU Yifei, CUI Yuwei. New Primary/Backup Scheduling Algorithm in Heterogeneous Distributed Systems [J]. Computer Engineering and Applications, 2019, 55(21): 93-98.
[7]	SUN Bo, JIANG Ping, ZHOU Genrong, LU Yitian. Application of Improved Genetic Algorithm in Path Planning of Mobile Robots [J]. Computer Engineering and Applications, 2019, 55(17): 162-168.
[8]	ZHANG Jun, HE Ketai. Study on Hybrid Genetic and Simulated Annealing Algorithm for Three-Dimensional Packing Problems [J]. Computer Engineering and Applications, 2019, 55(14): 32-39.
[9]	YU Wuyang, ZHOU Yang. Study of Unequal Area Facility Layout Problem with Improved Flexible Bay Structure [J]. Computer Engineering and Applications, 2019, 55(14): 221-227.
[10]	LIU Lanfen, YANG Xinfeng. Searching Algorithm for Efficient Paths Based on Hybrid Genetic Algorithm [J]. Computer Engineering and Applications, 2019, 55(11): 244-249.
[11]	MAO Lili, ZHANG Zeqiang, ZHU Lixia. Hybrid scatter search algorithm with simulated annealing for corridor allocation problem [J]. Computer Engineering and Applications, 2018, 54(3): 243-249.
[12]	SUN Xianming, FAN Xiaoguang, ZHUO Zhenfu, CONG Wei, CHEN Shaohua. New method of two classes feature extraction based on kernel linear discriminant analysis following integrated time and frequency domains [J]. Computer Engineering and Applications, 2018, 54(3): 115-119.
[13]	XIA Yichong, CHEN Qiulian, SONG Renkun. Packing of rectangles using adaptive genetic simulated annealing algorithm [J]. Computer Engineering and Applications, 2018, 54(22): 229-232.
[14]	WANG Kaipu, ZHANG Zeqiang, ZOU Binsen, MAO Lili. Pareto optimization for multi-objective disassembly line balancing with fuzzy operation times [J]. Computer Engineering and Applications, 2018, 54(1): 256-263.
[15]	ZOU Jitao1, XU Lan2, ZENG Xiangchun1, WANG Youzheng1, WANG Chao1. Research on assembly line balancing?problem?considering?multi-professional coordination [J]. Computer Engineering and Applications, 2017, 53(7): 263-270.

Lower bounds for Ramsey numbers based on simulated annealing algorithm

求解Ramsey数下界的模拟退火算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics