文档类型
文章
出版日期
6-15-2019
出版来源
离散应用数学
卷号
262年
第一页
72年
最后一页
82年
出版商
爱思唯尔
石头
0166 - 218 x
文摘
连通图,给出一个简单的用卵石铺配置(或只是配置)是一个函数的顶点设置为非负整数。一个用卵石铺移动相邻顶点删除两个石子从一个顶点并添加一个石子。一个顶点r据说是可获得的从配置如果存在一系列用卵石铺移动至少一个卵石的地方r。一个配置可以解决的如果每一个顶点都是可获得的。的用卵石铺数量π(G)的图G是最小整数,这样每一个配置的大小π(G)在G是可以解决的。一个图表G据说满足吗two-pebbling财产如果由于任何配置超过2π(G)——问鹅卵石,问顶点的鹅卵石,两个石子可以搬到任何顶点的G。Lemke图是一个图表,不满足two-pebbling财产。在本文中,我们提出了一种新的算法来确定一个顶点是否可以与一个给定的配置,如果配置图是可以解决的。我们还讨论简单的算法来计算用卵石铺数量和确定是否一个图two-pebbling属性。最后,我们使用这些算法来确定所有Lemke图最多9点,发现很多未知Lemke图表。
关键字
图用卵石铺,算法,Lemke图
建议引用
存储库的引用:库萨克,查尔斯·a·;绿色,亚伦;Bekmetjev Airat;和权力,马克,“图用卵石铺算法和Lemke图”(2019)。教师的出版物。1486年论文。
https://digitalcommons.m.icarseries.com/faculty_publications/1486
发表在:离散应用数学,卷262,6月15日,2019年,页72 - 82。版权©2019爱思唯尔。
评论
Creative Commons Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)
查尔斯·a·库萨克,亚伦绿色Airat Bekmetjev,标志着权力,图用卵石铺算法和Lemke图形、离散应用数学,262卷,2019年,页72 - 82,https://doi.org/10.1016/j.dam.2019.02.028。