教师的导师(s)
查尔斯•库萨克博士世界杯荷兰vs厄瓜多尔走地
文档类型
海报
事件日期
4-13-2012
文摘
给出一个简单的连通图,用卵石铺配置是一个函数的顶点设置为非负整数。用卵石铺移动相邻顶点删除两个石子从一个顶点并添加一个石子。下一个顶点r据说可以配置如果存在一系列用卵石铺移动一个石子的地方在r。配置是可以解决的,如果每一个顶点都是可获得的。我们证明严格边界的顶点和两个和三个石子的数量可以存在于一个无法解决的配置在一个直径2图的图形的大小。我们还证明,确定可达性一个顶点的np完备性,即使在直径2的图。
建议引用
存储库的引用:刘易斯,盖;辛普森,丹尼尔;Taggart,山姆,“直径用卵石铺两个图形的复杂性”(2012)。11年度庆典本科生研究和创意表现的(2012)。105年论文。
https://digitalcommons.m.icarseries.com/curcp_11/105
2012年4月13日。
评论
这项工作是由美国国家科学基金会支持的研究经验为本科生项目批准号0851293。