8
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Shortest Reconfiguration Sequence for Sliding Tokens on Spiders

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          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 sliding exactly one token along an edge in the graph. It is one of the representative reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. For a yes-instance of a reconfiguration problem, finding a shortest reconfiguration sequence has a different aspect. In general, even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be \(\mathsf{NP}\)-hard to find a shortest sequence between them. In this paper, we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for spiders (i.e., trees having exactly one vertex of degree at least three).

          Related collections

          Most cited references7

          • Record: found
          • Abstract: not found
          • Article: not found

          PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Linear-time algorithm for sliding tokens on trees

              Bookmark
              • Record: found
              • Abstract: not found
              • Book Chapter: not found

              Polynomial-Time Algorithm for Sliding Tokens on Trees

                Bookmark

                Author and article information

                Journal
                21 June 2018
                Article
                1806.08291
                db693a62-35c7-4202-9401-9008c76ead64

                http://creativecommons.org/licenses/by/4.0/

                History
                Custom metadata
                21 pages, 15 figures
                cs.DS cs.DM math.CO

                Combinatorics,Data structures & Algorithms,Discrete mathematics & Graph theory

                Comments

                Comment on this article