标题
平面和外平面图中球化可达性和可解性的复杂性
文档类型
文章
出版日期
7-31-2014
出版来源
离散应用数学
卷号
172
第一页
62
最后一页
74
出版商
爱思唯尔科学公司
石头
0166 - 218 x
摘要
给定一个简单的连通图，a用卵石铺配置是从它的顶点集合到非负整数的函数。一个用卵石铺移动在相邻顶点之间，从一个顶点移除两个卵石，并将一个卵石添加到另一个顶点。顶点r是可获得的如果存在将至少一个卵石放在r上的卵石移动序列，则从一个构型中得到可以解决的如果每个顶点都是可达的。证明了平面图上顶点的可达性和构型的可解性是np完全的。我们还证明了可达性和可解性都可以在O(n)中确定6)时间在直径为2的平面图形上。最后，对于外平面图形，我们提出了确定可达性的线性算法和确定可解性的二次算法。为了证明这一结果，我们提供了线性算法来确定可以放置在路径端点和循环中两个相邻顶点上的所有可能的最大鹅卵石配置。
关键字
图卵石，平面，外平面，np完全，直径2图，循环
建议引用
路易斯，蒂莫西，查尔斯·a·库萨克，丽莎·迪昂。平面和外平面图中球化可达性和可解性的复杂性。离散应用数学172(2014年7月31日):62-74。doi: 10.1016 / j.dam.2014.03.008。
硬币
