随机图的
L （2，1）-标号混合人工蜂群算法A Hybrid Artificial Bee Colony Algorithm for
L （2，1）-Labelling of Random Graph- 武汉大学学报（理学版） 2021年67卷第2期 页码：158-164
- 作者机构：
1.兰州交通大学 电子与信息工程学院，甘肃 兰州 730070
- 作者简介：
孙 帅，男，硕士生，现从事图论算法及其应用研究。E-mail：775080496@qq.com
E-mail： lijingwen28@163.com
- 基金信息：国家自然科学基金(11461038)
DOI：10.14188/j.1671-8836.2020.0200
中图分类号：
扫 描 看 全 文
孙帅, 李敬文, 袁清厚. 随机图的
L （2，1）-标号混合人工蜂群算法[J]. 武汉大学学报（理学版）, 2021,67(2):158-164.SUN Shuai, LI Jingwen, YUAN Qinghou. A Hybrid Artificial Bee Colony Algorithm for
L （2，1）-Labelling of Random Graph[J]. J Wuhan Univ （Nat Sci Ed）, 2021,67(2):158-164.孙帅, 李敬文, 袁清厚. 随机图的
L （2，1）-标号混合人工蜂群算法[J]. 武汉大学学报（理学版）, 2021,67(2):158-164. DOI： 10.14188/j.1671-8836.2020.0200.SUN Shuai, LI Jingwen, YUAN Qinghou. A Hybrid Artificial Bee Colony Algorithm for
L （2，1）-Labelling of Random Graph[J]. J Wuhan Univ （Nat Sci Ed）, 2021,67(2):158-164. DOI： 10.14188/j.1671-8836.2020.0200.
摘要
为解决图的,L,（2，1）-标号问题，设计了一种全新的标号算法，该算法利用人工蜂群全局搜索能力强的优点来得到最优的,L,（2，1）-标号方案。为了加快算法的收敛速度，修改了部分搜索策略并采用改进后的CK算法对初始蜜源进行限制。实验结果表明，该算法可以有效地求解有限点内随机图的,L,（2，1）-标号且10个点内的简单连通图都满足Griggs的猜想。通过分析实验结果总结出有关,K,n,\,e,、,K,n,\2,e,、联图,K,n,↑,S,m,以及太阳图等的相关定理，并结合已有结果给出了新的猜想。
Abstract
In order to solve the problem ,L,(2,1)-labelling of graphs, a new labelling algorithm is designed to obtain the optimal ,L,(2,1)-labelling based on the advantages of strong global searching ability of artificial bee colony. Some search strategies are modified and the improved CK algorithm is used to limit the initial nectar source, which speeds up the convergence speed of the algorithm. It shows that the algorithm can effectively solve the ,L,(2,1)-labelling of random graphs within finite points according to experimental results, and simple connected graphs within 10 points satisfy Griggs’s conjecture. By analyzing the experimental results, we summarize the relevant theorems about ,K,n,\,e,K,n,\,2e, the composite graph ,K,n,↑,S,m, and the sun graph, and give new conjectures combining the existing results.
关键词
L（2，1）-标号标号数人工蜂群算法组合优化
Keywords
L(21)-labellinglabelling numberartificial bee colony(ABC) algorithmcombination optimization
references
HALE W K. Frequency assignment： Theory and applications ［J］. Proceedings of the IEEE， 1980，68（12）：1497–1514. DOI：10.1109/PROC.1980.11899http://dx.doi.org/10.1109/PROC.1980.11899.
GRIGGS J R， YEH R K. Labelling graphs with a condition at distance 2［J］. SIAM Journal on Discrete Mathematics， 1992， 5（4）： 586-595. DOI：10.1137/0405048http://dx.doi.org/10.1137/0405048.
CALAMONERI T. The L（h，k）-labelling problem： An updated survey and annotated bibliography［J］. The Computer Journal， 2011， 54（8）： 1344-1371. DOI：10.1093/comjnl/bxr037http://dx.doi.org/10.1093/comjnl/bxr037.
GONÇALVES D. On the L（p，1）-labelling of graphs ［J］. Discrete Mathematics， 2008， 308（8）： 1405-1414. DOI：10.1016/j.disc.2007.07.075http://dx.doi.org/10.1016/j.disc.2007.07.075.
CHANG G J ， KUO D . The L（2，1）-labeling problem on graphs ［J］. SIAM Journal on Discrete Mathematics， 1996， 9（2）：309-316. DOI：10.1137/S0895480193245339http://dx.doi.org/10.1137/S0895480193245339.
HASUNUMA T， ISHII T， ONO H， et al. A linear time algorithm for L（2，1）-labeling of trees ［J］. Algorithmica，2013，66（3）：35-46. DOI：10.1007/s00453-012-9657-zhttp://dx.doi.org/10.1007/s00453-012-9657-z.
CALAMONERI T， VOCCA P. On the approximability of the L（h，k）-labelling problem on bipartite graphs （extended abstract） ［C］// International Colloquium on Structural Information and Communication Complexity. Berlin： Springer， 2005： 65-77. DOI：10.1007/11429647_7http://dx.doi.org/10.1007/11429647_7.
ONO H， YAMANAKA H. A 116/13-approximation algorithm for L（2，1）-labeling of unit disk graphs ［C］// SOFSEM 2019： Theory and Practice of Computer Science （LNCS 11376）. Cham： Springer， 2019： 379-391. DOI：10.1007/978-3-030-10801-4_30http://dx.doi.org/10.1007/978-3-030-10801-4_30.
KARABOGA D. An Idea Based on Honey Bee Swarm for Numerical Optimization ［R］. Kayseri： Erciyes University，2005.
秦全德，程适，李丽，等.人工蜂群算法研究综述［J］.智能系统学报，2014，9（2）：127-135. DOI： 10.3969/j.issn.1673-4785.201309064http://dx.doi.org/10.3969/j.issn.1673-4785.201309064.
QIN Q D， CHENG S， LI L， et al. Artificial bee colony algorithm： A survey ［J］. CAAI Transactions on Intelligent Systems，2014，9（2）： 127-135. DOI： 10.3969/j.issn.1673-4785.201309064（Chhttp://dx.doi.org/10.3969/j.issn.1673-4785.201309064（Ch）.
何尧，刘建华，杨荣华.人工蜂群算法研究综述［J］.计算机应用研究，2018，35（5）：1281-1286. DOI：10.3969/j. issn. 1001- 3695.2018.05.001http://dx.doi.org/10.3969/j.issn.1001-3695.2018.05.001.
HE Y，LIU J H，YANG R H. Survey on artificial bee colony algorithm ［J］. Application Research of Computers， 2018，35（5）：1281-1286. DOI：10.3969/j. issn. 1001- 3695.2018.05.001（Chhttp://dx.doi.org/10.3969/j.issn.1001-3695.2018.05.001（Ch）.
顾彦波，李敬文，邵淑宏，等. 非边幻和图的若干定理及证明［J］.武汉大学学报（理学版），2020，66（3）：237-243. DOI： 10.14188/j.1671-8836.2019.0216http://dx.doi.org/10.14188/j.1671-8836.2019.0216.
GU Y B， LI J W， SHAO S H， et al. Some theorems and proofs of non-edge-magic total labeling graphs ［J］. Journal of Wuhan University （Natural Science Edition）， 2020， 66（3）：237-243. DOI：10. 14188/j.1671-8836.2019.0216（Chhttp://dx.doi.org/10.14188/j.1671-8836.2019.0216（Ch）.
谢建民，姚兵，赵廷刚.广义太阳图Sm，n奇优雅标号算法及实现［J］.山东大学学报（理学版），2016，51（4）：79-85+89. DOI： 10.6040/j.issn.1671-9352.0.2014.404http://dx.doi.org/10.6040/j.issn.1671-9352.0.2014.404.
XIE J M，YAO B，ZHAO T G. An algorithm and its implementation for odd-elegant labeling of general sun graph Sm，n ［J］. Journal of Shandong University（Natural Science）， 2016，51（4）：79-85+89. DOI： 10.6040/j.issn.1671-9352.0.2014.404（Chhttp://dx.doi.org/10.6040/j.issn.1671-9352.0.2014.404（Ch）.
MCKAY B D， PIPERNO A. Practical graph isomorphism， Ⅱ ［J］. Journal of Symbolic Computation， 2014， 60： 94-112. DOI： 10.1016/j.jsc.2013.09.003http://dx.doi.org/10.1016/j.jsc.2013.09.003.
0
浏览量
24
下载量
2
CSCD
- 网络PDF下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 地址：湖北省武汉市武昌区武汉大学文理学部本科生院楼北楼504
- 联系电话：027-68756952 Email：whdz@whu.edu.cn
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies
- 总访问量：223640