Shortest reconfiguration of sliding tokens on subclasses of interval graphs

DOI10.1016/J.TCS.2021.02.019MaRDI QIDQ2658043zbMATHOpenAlexFDO

Authors Takeshi Yamada, Ryuhei Uehara

Publication date 18 March 2021

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

Full work available at URL https://doi.org/10.1016/j.tcs.2021.02.019

zbMATH Keywords

independent setcaterpillardetoursliding tokenreconfiguration problemshortest sequence

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Linear-time algorithm for sliding tokens on trees
• Token sliding on chordal graphs
• Polynomial-time algorithm for sliding tokens on trees
• Sliding tokens on block graphs

Cites work

• A short proof that `proper = unit'
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Complexity of independent set reconfigurability problems
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Games, puzzles, and computation
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• On the diameter of reconfiguration graphs for vertex colourings
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Parameterized complexity of graph constraint logic
• Reconfiguration over tree decompositions
• Reconfiguring independent sets in claw-free graphs
• Shortest paths between shortest paths
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Sliding token on bipartite permutation graphs
• Sliding tokens on a cactus
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The complexity of independent set reconfiguration on bipartite graphs
• Token sliding on chordal graphs

Cited in

(10)

• Sliding token on bipartite permutation graphs
• 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Shortest reconfiguration of perfect matchings via alternating cycles
• Polynomial-time algorithm for sliding tokens on trees
• Token sliding on split graphs
• Sliding tokens on block graphs
• Computational complexity of puzzles and related topics
• Token sliding on chordal graphs
• On finding short reconfiguration sequences between independent sets

This page was built for publication: Shortest reconfiguration of sliding tokens on subclasses of interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2658043)