Polynomial-Time Algorithm for Sliding Tokens on Trees
Polynomial-Time Algorithm for Sliding Tokens on Trees
复制标题
树上滑动令牌的多项式时间算法
DOI：
10.1007/978-3-319-13075-0_31
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Takeshi Yamada
中科院分区：
文献类型：
--
作者：
Erik D. Demaine;Martin L. Demaine;Eli Fox-Epstein;Duc A. Hoang;Takehiro Ito;Hirotaka Ono;Yota Otachi;Ryuhei Uehara;Takeshi Yamada
假设我们给定一个图的两个独立的集合I和I，使得$${{\varvec{I}_{B}$$=I，并想象在I中的每个顶点上放置一个标记。然后，滑动标记问题是确定是否存在一个独立集的序列，该序列转换I和I，使得序列中的每个独立集都是通过沿着图中的一条边滑动一个标记而从前一个独立集产生的。这个问题是已知的PSPACE完全的平面图，也为有界树宽图。在本文中，我们证明了这个问题是可解的树在二次时间。我们的证明是建设性的：对于一个是的实例，我们可以找到一个实际的序列的独立集之间的IandI，其长度（即，令牌载玻片的数量）是二次的。我们注意到，存在一个无限的家庭的情况下，任何序列的路径需要平方长度。
Suppose that we are given two independent setsIandIof a graph such that$${{\varvec{I}}}_{b}$$=I, and imagine that a token is placed on each vertex inI. Then, thesliding tokenproblem is to determine whether there exists a sequence of independent sets which transformsIandIso that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we show that the problem is solvable for trees in quadratic time. Our proof is constructive: for a yes-instance, we can find an actual sequence of independent sets betweenIandIwhose length (i.e., the number of token-slides) is quadratic. We note that there exists an infinite family of instances on paths for which any sequence requires quadratic length.
登录
查看更多内容
在无爪图中重新配置独立集
DOI：
10.1007/978-3-319-08404-6_8
发表时间：
2014
期刊：
ArXiv
影响因子：
--
作者：
P. Bonsma;M. Kaminski;Marcin Wrochna
通讯作者：
Marcin Wrochna
游戏、谜题和计算
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
R. Hearn;E. Demaine
通讯作者：
E. Demaine
重新路由最短路径的复杂性
影响因子：
1.1
作者：
P. Bonsma
通讯作者：
P. Bonsma
DOI：
10.1007/978-3-319-13524-3_21
发表时间：
2014
期刊：
--
影响因子：
--
作者：
A. E. Mouawad;N. Nishimura;Venkatesh Raman;Marcin Wrochna
通讯作者：
Marcin Wrochna
最短路径之间的最短路径
DOI：
10.1016/j.tcs.2011.05.021
发表时间：
2011
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
M. Kaminski;P. Medvedev;Martin Milanič
通讯作者：
Martin Milanič