Fixed-Parameter Tractability of Token Jumping on Planar Graphs
Fixed-Parameter Tractability of Token Jumping on Planar Graphs
复制标题
平面图上令牌跳跃的固定参数可处理性
DOI：
10.1007/978-3-319-13075-0_17
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Hirotaka Ono
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Marcin Kaminski;Hirotaka Ono
假设我们被赋予两个独立的图集，并且想象在中的每个顶点上放置一个记号。标记跳跃问题是确定是否存在相同基数的独立集序列，该序列中的每个独立集通过恰好将一个标记移动到另一个顶点而得到该序列中的每个独立集。即使对于最大度为3的平面图，这个问题也是PSPACE-完全的，而对于一般的图，当用记号数参数化时，这个问题是W[1]-困难的。本文给出了平面图上令牌跳跃的一个固定参数算法，其中参数仅为令牌数。此外，该算法还可以进行修改，以便为YES实例找到最短序列。算法的相同方案可以应用于更广泛的图类，这些图禁止一个完全二部图有一个固定整数的子图。
Suppose that we are given two independent setsandof a graph such that, and imagine that a token is placed on each vertex in. Thetoken jumpingproblem is to determine whether there exists a sequence of independent sets of the same cardinality which transformsintoso that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. This problem is known to be PSPACE-complete even for planar graphs of maximum degree three, and W[1]-hard for general graphs when parameterized by the number of tokens. In this paper, we present a fixed-parameter algorithm fortoken jumpingon planar graphs, where the parameter is only the number of tokens. Furthermore, the algorithm can be modified so that it finds a shortest sequence for a yes-instance. The same scheme of the algorithms can be applied to a wider class of graphs which forbid a complete bipartite graphas a subgraph for a fixed integer.
登录
查看更多内容
在无爪图中重新配置独立集
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
有界长度图重新着色的复杂性
DOI：
10.1002/jgt.22870
发表时间：
2014
期刊：
ArXiv
影响因子：
--
作者：
P. Bonsma;A. E. Mouawad
通讯作者：
A. E. Mouawad
DOI：
10.1007/978-3-319-13524-3_21
发表时间：
2014
期刊：
--
影响因子：
--
作者：
A. E. Mouawad;N. Nishimura;Venkatesh Raman;Marcin Wrochna
通讯作者：
Marcin Wrochna
影响因子：
1.1
作者：
Kaminski, Marcin;Medvedev, Paul;Milanic, Martin
通讯作者：
Milanic, Martin