Linear-Time Algorithm for Sliding Tokens on Trees

Linear-Time Algorithm for Sliding Tokens on Trees

Suppose that we are given two independent sets I [subscript b] and I [subscript r] of a graph such that ∣ I [subscript b] ∣ = ∣ I [subscript r] ∣, and imagine that a token is placed on each vertex in I [subscript b]. Then, the sliding token problem is to determine whether there exists a sequence of...

Full description

Bibliographic Details
Main Authors: Demaine, Erik D., Demaine, Martin L., Fox-Epstein, Eli, Hoang, Duc A., Ito, Takehiro, Ono, Hirotaka, Otachi, Yota, Uehara, Ryuhei, Yamada, Takeshi
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Springer-Verlag 2015
Online Access:http://hdl.handle.net/1721.1/99985
https://orcid.org/0000-0003-3803-5703

Internet

http://hdl.handle.net/1721.1/99985
https://orcid.org/0000-0003-3803-5703

Similar Items