标题

用卵石铺的复杂性可达性和溶解度在平面和外平面的图形

文档类型

文章

出版日期

7-31-2014

出版来源

离散应用数学

卷号

172年

第一页

62年

最后一页

74年

出版商

爱思唯尔科学BV

石头

0166 - 218 x

文摘

连通图,给出一个简单的用卵石铺配置是一个函数的顶点设置为非负整数。一个用卵石铺移动相邻顶点删除两个石子从一个顶点并添加一个石子。r是一个顶点可获得的从一个配置如果存在一系列用卵石铺移动地方至少一个石子r。一个配置可以解决的如果每一个顶点都是可获得的。我们证明确定一个顶点的可达性和溶解度配置的非完全多项式在平面图形。我们还证明,可达性和溶解度都可以确定在O (n6在平面图形与直径2)时间。最后,对于外平面的图形,我们提出一个线性算法确定可达性和二次算法确定可解性。为了证明这个结果,我们提供线性算法来确定所有可能的最大配置端点的鹅卵石,可以放在两个相邻顶点的路径和一个循环。

关键字

图用卵石铺,平面、外平面的非完全多项式,直径2图,周期

全文链接
硬币