Results 1 to 10 of about 69 (53)
On Girth and the Parameterized Complexity of Token Sliding and Token Jumping [PDF]
Algorithmica, 2021 In the Token Jumping problem we are given a graph $G = (V,E)$ and two independent sets $S$ and $T$ of $G$, each of size $k \geq 1$. The goal is to determine whether there exists a sequence of $k$-sized independent sets in $G$, $\langle S_0, S_1, \ldots, S_\ell \rangle$, such that for every $i$, $|S_i| = k$, $S_i$ is an independent set, $S = S_0$, $S_ ...
Clement Dallard +2 more
exaly +9 more sources
Dominating sets reconfiguration under token sliding [PDF]
Discrete Applied Mathematics, 2021 Let $G$ be a graph and $D_s$ and $D_t$ be two dominating sets of $G$ of size $k$. Does there exist a sequence $\langle D_0 = D_s, D_1, \ldots, D_{\ell-1}, D_\ell = D_t \rangle$ of dominating sets of $G$ such that $D_{i+1}$ can be obtained from $D_i$ by replacing one vertex with one of its neighbors?
Marthe Bonamy, Paul Dorbec
exaly +5 more sources
Linear-time algorithm for sliding tokens on trees [PDF]
Theoretical Computer Science, 2015 Suppose that we are given two independent sets $I_b$ and $I_r$ of a graph such that $|I_b|=|I_r|$, and imagine that a token is placed on each vertex in $I_b$. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms $I_b$ into $I_r$ so that each independent set in the sequence results from the
Yota Otachi +2 more
exaly +8 more sources
Token Sliding on Graphs of Girth Five
Lecture Notes in Computer Science, 2022 AbstractIn the Token Sliding problem we are given a graph G and two independent sets $$I_s$$ I s and $$I_t$$ I t in G of size $$k \ge 1$$
Sebastian Siebertz +2 more
exaly +5 more sources
Token Sliding on Split Graphs [PDF]
Theory of Computing Systems, 2020 We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent.
Remy Belmonte +2 more
exaly +6 more sources
Token Sliding on Chordal Graphs [PDF]
Lecture Notes in Computer Science, 2017 Let I be an independent set of a graph G. Imagine that a token is located on any vertex of I. We can now move the tokens of I along the edges of the graph as long as the set of tokens still defines an independent set of G. Given two independent sets I and J, the Token Sliding problem consists in deciding whether there exists a sequence of independent ...
Nicolas Bousquet +2 more
exaly +3 more sources
On Reconfiguration Graphs of Independent Sets Under Token Sliding
Graphs and Combinatorics, 2023 17 pages, 12 figures, accepted to Graphs and ...
Duc A Hoang, Avis David, David Avis
exaly +4 more sources
Shortest Dominating Set Reconfiguration Under Token Sliding
Lecture Notes in Computer Science, 2023 In this paper, we present novel algorithms that efficiently compute a shortest reconfiguration sequence between two given dominating sets in trees and interval graphs under the Token Sliding model. In this problem, a graph is provided along with its two dominating sets, which can be imagined as tokens placed on vertices.
Jan Matyas Kristan, Jakub Svoboda
exaly +3 more sources
Shortest Reconfiguration Sequence for Sliding Tokens on Spiders [PDF]
Lecture Notes in Computer Science, 2019 Suppose that two independent sets $I$ and $J$ of a graph with $\vert I \vert = \vert J \vert$ are given, and a token is placed on each vertex in $I$. The Sliding Token problem is to determine whether there exists a sequence of independent sets which transforms $I$ into $J$ so that each independent set in the sequence results from the previous one by ...
Amanj Khorramian +2 more
exaly +3 more sources
TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$
Theory and Applications of Graphs, 2023 A k-path vertex cover (k-PVC) of a graph G is a vertex subset I such that each path on k vertices in G contains at least one member of I. Imagine that a token is placed on each vertex of a k-PVC.
Duc A. Hoang
doaj +1 more source