Polynomial-time algorithm for sliding tokens on trees

DOI10.1007/978-3-319-13075-0_31MaRDI QIDQ2942646zbMATH OpenOpenAlexFDO

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

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/99985

zbMATH Keywords

independent setsliding token

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Linear-time algorithm for sliding tokens on trees
• Sliding tokens on a cactus
• Sliding tokens on block graphs
• Token sliding on chordal graphs
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs

Cited in

(20)

• Token sliding on chordal graphs
• On girth and the parameterized complexity of token sliding and token jumping
• Token sliding on split graphs
• Shortest reconfiguration sequence for sliding tokens on spiders
• How to sort by walking and swapping on paths and trees
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Fixed-parameter tractability of token jumping on planar graphs
• Sliding tokens on block graphs
• Sliding token on bipartite permutation graphs
• Sliding tokens on a cactus
• Linear-time algorithm for sliding tokens on trees
• On the Parameterized Complexity for Token Jumping on Graphs
• Token sliding on graphs of girth five
• scientific article; zbMATH DE number 7765402 (Why is no real title available?)
• Token sliding on graphs of girth five
• On finding short reconfiguration sequences between independent sets
• On solution discovery via reconfiguration
• A survey on the parameterized complexity of reconfiguration problems
• Token sliding reconfiguration on DAGs

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

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