2 citations · 3 across the 6 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2019
Reconfiguring Undirected Paths
Erik D. Demaine, David Eppstein, Adam Hesterberg +4
We consider problems in which a simple path of fixed length, in an undirected graph, is to be shifted from a start position to a goal position by moves that add an edge to either e…
cs.DS2018
Shortest Reconfiguration Sequence for Sliding Tokens on Spiders
Duc A. Hoang, Amanj Khorramian, Ryuhei Uehara
Suppose that two independent sets and of a graph with are given, and a token is placed on each vertex in . The Sliding Token problem is t…
cs.DS2018
Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil +5
We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices ca…