22 citations · 107 across the 16 of their papers we have counts for
Showing 2014 · cs.CCShow all
3 papers · 2 filters
cs.CC2014
Homomorphism reconfiguration via homotopy
Marcin Wrochna
We consider the following problem for a fixed graph H: given a graph G and two H-colorings of G, i.e. homomorphisms from G to H, can one be transformed (reconfigured) into the othe…
cs.CC2014
Reconfiguration in bounded bandwidth and treedepth
Marcin Wrochna
We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth. The essential step is noticing the similarity…
cs.CC2014
Reconfiguration over tree decompositions
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman +1
A vertex-subset graph problem defines which subsets of the vertices of an input graph are feasible solutions. The reconfiguration version of a vertex-subset problem asks wh…