Reconfiguring Independent Sets in Claw-Free Graphs

Reconfiguring Independent Sets in Claw-Free Graphs
复制标题

在无爪图中重新配置独立集

DOI：
10.1007/978-3-319-08404-6_8
复制
发表时间：
2014
期刊：
ArXiv
影响因子：
--
通讯作者：
Marcin Wrochna
Marcin Wrochna
中科院分区：
--
文献类型：
--
作者：
P. Bonsma;M. Kaminski;Marcin Wrochna

文献摘要

被引文献

相似文献

我们提出了一种多项式时间算法，鉴于在无爪图G中的两个独立集中，该算法决定是否可以通过一系列基本步骤转换为另一个集合。每个基本步骤都是从当前独立集s中删除顶点v，并添加一个新的顶点W（不在s中），以使结果再次是独立的集合。我们还考虑了V和W必须相邻的更受限制的模型。
We present a polynomial-time algorithm that, given two independent sets in a claw-free graph G, decides whether one can be transformed into the other by a sequence of elementary steps. Each elementary step is to remove a vertex v from the current independent set S and to add a new vertex w (not in S) such that the result is again an independent set. We also consider the more restricted model where v and w have to be adjacent.