Linear-time algorithm for sliding tokens on trees
From MaRDI portal
Publication:496016
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
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
