Linear-time algorithm for sliding tokens on trees

DOI10.1016/j.tcs.2015.07.037zbMath1329.68135arXiv1406.6576OpenAlexW2169085828MaRDI QIDQ496016

Erik D. Demaine, Takeshi Yamada, Yota Otachi, Ryuhei Uehara, Takehiro Ito, Duc A. Hoang, Eli Fox-Epstein, Hirotaka Ono, Martin L. Demaine

Publication date: 16 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.6576

zbMATH Keywords

treegraph algorithmindependent setcombinatorial reconfigurationsliding token

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (28)

Reconfiguration of colorable sets in classes of perfect graphs ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Distributed reconfiguration of maximal independent sets ⋮ Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Reconfiguration of connected graph partitions ⋮ Galactic token sliding ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ On reconfiguration graphs of independent sets under token sliding ⋮ Extremal independent set reconfiguration ⋮ The Complexity of (List) Edge-Coloring Reconfiguration Problem ⋮ Sliding Tokens on Block Graphs ⋮ The complexity of dominating set reconfiguration ⋮ Unnamed Item ⋮ Complexity of token swapping and its variants ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Token sliding on split graphs ⋮ Reconfiguration of Steiner Trees in an Unweighted Graph ⋮ The Perfect Matching Reconfiguration Problem ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints

Cites Work

• Unnamed Item
• The complexity of rerouting shortest paths
• Complexity of independent set reconfigurability problems
• Approximability of the subset sum reconfiguration problem
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Reconfiguration of list edge-colorings in a graph
• Shortest paths between shortest paths
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• A partial k-arboretum of graphs with bounded treewidth
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Polynomial-Time Algorithm for Sliding Tokens on Trees
• Independent Set Reconfiguration in Cographs
• Reconfiguration over Tree Decompositions
• Finding paths between 3-colorings
• Reconfiguring Independent Sets in Claw-Free Graphs
• On the Parameterized Complexity for Token Jumping on Graphs
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Linear-time algorithm for sliding tokens on trees