Web Survey on Combinatorial Reconfiguration

(about this survey)

Filters:
Problems: all
Choose Problem

Authors: all
Choose Author


[1]
Robert A. Hearn and Erik D. Demaine,
PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation,
Theoretical Computer Science 343(1-2), pp. 72-96, 2005. (LINK)

[2]
Bojan Mohar,
Kempe equivalence of colorings,
Proceedings of a Conference in Memory of Claude Berge, Graph Theory in Paris, pp. 287-297, 2006. (LINK)

[3]
Luis Cereceda, Jan van den Heuvel and Matthew Johnson,
Connectedness of the graph of vertex-colourings,
Discrete Mathematics 308(5-6), pp. 913-919, 2008. (LINK)

[4]
Paul S. Bonsma and Luis Cereceda,
Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances,
Theoretical Computer Science 410(50), pp. 5215-5226, 2009. (LINK)

[5]
Luis Cereceda, Jan van den Heuvel and Matthew Johnson,
Mixing 3-colourings in bipartite graphs,
European Journal of Combinatorics 30(7), pp. 1593-1606, 2009. (LINK)

[6]
Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva and Christos H. Papadimitriou,
The connectivity of Boolean satisfiability: computational and structural dichotomies,
SIAM Journal on Computing 38(6), pp. 2330-2355, 2009. (LINK)

[7]
Kazuhisa Makino, Suguru Tamaki and Masaki Yamamoto,
On the Boolean connectivity problem for Horn relations,
Discrete Applied Mathematics 158(18), pp. 2024-2030, 2010. (LINK)

[8]
Somkiat Trakultraipruk,
Connectedness of strong k-colour graphs,
arXiv 1009.4440, 2010. (LINK)

[9]
Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel and Daniël Paulusma,
On the diameter of reconfiguration graphs for vertex colourings,
Proceedings of the 6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2011), Electronic Notes in Discrete Mathematics 38, pp. 161-166, 2011. (LINK)

[10]
Luis Cereceda, Jan van den Heuvel and Matthew Johnson,
Finding paths between 3-colorings,
Journal of Graph Theory 67(1), pp. 69-82, 2011. (LINK)

[11]
Takehiro Ito, Erik D. Demaine, Nicholas J.A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara and Yushi Uno,
On the complexity of reconfiguration problems,
Theoretical Computer Science 412(12-14), pp. 1054-1065, 2011. (LINK)

[12]
Marcin Kamiński, Paul Medvedev and Martin Milanič,
Shortest paths between shortest paths,
Theoretical Computer Science 412(39), pp. 5205-5210, 2011. (LINK)

[13]
Kazuhisa Makino, Suguru Tamaki and Masaki Yamamoto,
An exact algorithm for the Boolean connectivity problem for k-CNF,
Theoretical Computer Science 412(35), pp. 4613-4618, 2011. (LINK)

[14]
Takehiro Ito, Marcin Kamiński and Erik D. Demaine,
Reconfiguration of list edge-colorings in a graph,
Discrete Applied Mathematics 160(15), pp. 2199-2207, 2012. (LINK)

[15]
Takehiro Ito, Kazuto Kawamura and Xiao Zhou,
An improved sufficient condition for reconfiguration of list edge-colorings in a tree,
IEICE Transactions on Information and Systems E95-D(3), pp. 737-745, 2012. (LINK)

[16]
Marcin Kamiński, Paul Medvedev and Martin Milanič,
Complexity of independent set reconfigurability problems,
Theoretical Computer Science 439, pp. 9-15, 2012. (LINK)

[17]
Jessica McDonald, Bojan Mohar and Diego Scheide,
Kempe equivalence of edge-colorings in subcubic and subquartic graphs,
Journal of Graph Theory 70(2), pp. 226-239, 2012. (LINK)

[18]
Marthe Bonamy and Nicolas Bousquet,
Recoloring bounded treewidth graphs,
Proceedings of the 7th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2013), Electronic Notes in Discrete Mathematics 44, pp. 257-262, 2013. (LINK)

[19]
Paul S. Bonsma,
The complexity of rerouting shortest paths,
Theoretical Computer Science 510, pp. 1-12, 2013. (LINK)

[20]
Sarah-Marie Belcastro and Ruth Haas,
Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs,
Discrete Mathematics 325, pp. 77-84, 2014. (LINK)

[21]
Marthe Bonamy and Nicolas Bousquet,
Reconfiguring independent sets in cographs,
arXiv 1406.1433, 2014. (LINK)

[22]
Marthe Bonamy and Nicolas Bousquet,
Recoloring graphs via tree decompositions,
arXiv 1403.6386, 2014. (LINK)

[23]
Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel and Daniël Paulusma,
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs,
Journal of Combinatorial Optimization 27(1), pp. 132-143, 2014. (LINK)

[24]
Paul S. Bonsma, Marcin Kamiński and Marcin Wrochna,
Reconfiguring independent sets in claw-free graphs,
Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), Lecture Notes in Computer Science 8503, pp. 86-97, 2014. (LINK)

[25]
Paul S. Bonsma, Amer E. Mouawad, Naomi Nishimura and Venkatesh Raman,
The complexity of bounded length graph recoloring and CSP reconfiguration,
Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), Lecture Notes in Computer Science 8894, pp. 110-121, 2014. (LINK)

[26]
Takehiro Ito and Erik D. Demaine,
Approximability of the subset sum reconfiguration problem,
Journal of Combinatorial Optimization 28(3), pp. 639-654, 2014. (LINK)

[27]
Takehiro Ito, Marcin Kamiński and Hirotaka Ono,
Fixed-parameter tractability of token jumping on planar graphs,
Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), Lecture Notes in Computer Science 8889, pp. 208-219, 2014. (LINK)

[28]
Takehiro Ito, Kazuto Kawamura, Hirotaka Ono and Xiao Zhou,
Reconfiguration of list L(2,1)-labelings in a graph,
Theoretical Computer Science 544, pp. 84-97, 2014. (LINK)

[29]
Amer E. Mouawad, Naomi Nishimura and Venkatesh Raman,
Vertex cover reconfiguration and beyond,
Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), Lecture Notes in Computer Science 8889, pp. 452-463, 2014. (LINK)

[30]
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman and Marcin Wrochna,
Reconfiguration over tree decompositions,
Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), Lecture Notes in Computer Science 8894, pp. 246-257, 2014. (LINK)

[31]
Marcin Wrochna,
Reconfiguration in bounded bandwidth and treedepth,
arXiv 1405.0847, 2014. (LINK)

[32]
Marthe Bonamy, Nicolas Bousquet, Carl Feghali and Matthew Johnson,
On a conjecture of Mohar concerning Kempe equivalence of regular graphs,
arXiv 1510.06964, 2015. (LINK)

[33]
Richard C. Brewster and Jonathan A. Noel,
Mixing homomorphisms, recolorings, and extending circular precolorings,
Journal of Graph Theory 80(3), pp. 173-198, 2015. (LINK)

[34]
Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara and Takeshi Yamada,
Linear-time algorithm for sliding tokens on trees,
Theoretical Computer Science 600, pp. 132-142, 2015. (LINK)

[35]
Eli Fox-Epstein, Duc A. Hoang, Yota Otachi and Ryuhei Uehara,
Sliding token on bipartite permutation graphs,
Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science 9472, pp. 237-247, 2015. (LINK)

[36]
Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou,
The list coloring reconfiguration problem for bounded pathwidth graphs,
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98-A(6), pp. 1168-1178, 2015. (LINK)

[37]
Takehiro Ito, Hirotaka Ono and Yota Otachi,
Reconfiguration of cliques in a graph,
Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC 2015), Lecture Notes in Computer Science 9076, pp. 212-223, 2015. (LINK)

[38]
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan and Saket Saurabh,
Reconfiguration on sparse graphs,
Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015), Lecture Notes in Computer Science 9214, pp. 506-517, 2015. (LINK)

[39]
Daniel C. McDonald,
Connectedness and Hamiltonicity of graphs on vertex colorings,
arXiv 1507.05344, 2015. (LINK)

[40]
Moritz Mühlenthaler,
Degree-constrained subgraph reconfiguration is in P,
Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), Lecture Notes in Computer Science 9235, pp. 505-516, 2015. (LINK)

[41]
Marcin Wrochna,
Homomorphism reconfiguration via homotopy,
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Leibniz International Proceedings in Informatics 30, pp. 730-742, 2015. (LINK)

[42]
Tom C. van der Zanden,
Parameterized complexity of graph constraint logic,
Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Leibniz International Proceedings in Informatics 43, pp. 282-293, 2015. (LINK)

[43]
Julie Beier, Janet Fierson, Ruth Haas, Heather M. Russell and Kara Shavo,
Classifying coloring graphs,
Discrete Mathematics 339(8), pp. 2100-2112, 2016. (LINK)

[44]
Mark de Berg, Bart M.P. Jansen and Debankur Mukherjee,
Independent-set reconfiguration thresholds of hereditary graph classes,
Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), Leibniz International Proceedings in Informatics 65, pp. 34:1-34:15, 2016. (LINK)

[45]
Paul S. Bonsma,
Independent set reconfiguration in cographs and their generalizations,
Journal of Graph Theory 83(2), pp. 164-195, 2016. (LINK)

[46]
Paul S. Bonsma and Daniël Paulusma,
Using contracted solution graphs for solving reconfiguration problems,
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Leibniz International Proceedings in Informatics 58, pp. 20:01-20:15, 2016. (LINK)

[47]
Nicolas Bousquet and Guillem Perarnau,
Fast recoloring of sparse graphs,
European Journal of Combinatorics 52(Part A), pp. 1-11, 2016. (LINK)

[48]
Richard C. Brewster, Sean McGuinness, Benjamin Moore and Jonathan A. Noel,
A dichotomy theorem for circular colouring reconfiguration,
Theoretical Computer Science 639, pp. 1-13, 2016. (LINK)

[49]
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel and Daniël Paulusma,
Finding shortest paths between graph colourings,
Algorithmica 75(2), pp. 295-321, 2016. (LINK)

[50]
Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki and Youcef Tebbal,
The complexity of dominating set reconfiguration,
Theoretical Computer Science 651, pp. 37-49, 2016. (LINK)

[51]
Duc A. Hoang and Ryuhei Uehara,
Sliding tokens on a cactus,
Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), Leibniz International Proceedings in Informatics 64, pp. 37:1-37:26, 2016. (LINK)

[52]
Takehiro Ito, Hiroyuki Nooka and Xiao Zhou,
Reconfiguration of vertex covers in a graph,
IEICE Transactions on Information and Systems E99-D(3), pp. 598-606, 2016. (LINK)

[53]
Akira Suzuki, Amer E. Mouawad and Naomi Nishimura,
Reconfiguration of dominating sets,
Journal of Combinatorial Optimization 32(4), pp. 1182-1195, 2016. (LINK)

[54]
Kunihiro Wasa, Katsuhisa Yamanaka and Hiroki Arimura,
The complexity of induced tree reconfiguration problems,
Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA 2016), Lecture Notes in Computer Science 9618, pp. 330-342, 2016. (LINK)

[55]
Takeshi Yamada and Ryuhei Uehara,
Shortest reconfiguration of sliding tokens on a caterpillar,
Proceedings of the 10th International Workshop on Algorithms and Computation (WALCOM 2016), Lecture Notes in Computer Science 9627, pp. 236-248, 2016. (LINK)

[56]
Paul S. Bonsma,
Rerouting shortest paths in planar graphs,
Discrete Applied Mathematics 231, pp. 95-112, 2017. (LINK)

[57]
Nicolas Bousquet, Arnaud Mary and Aline Parreau,
Token jumping in minor-closed classes,
Proceedings of the 21st International Symposium on Fundamentals of Computation Theory (FCT 2017), Lecture Notes in Computer Science 10472, pp. 136-149, 2017. (LINK)

[58]
Davood Fatehi, Saeid Alikhani and Abdul Jalil M. Khalaf,
The k-independent graph of a graph,
Advances and Applications in Discrete Mathematics 18(1), pp. 45-56, 2017. (LINK)

[59]
Carl Feghali, Matthew Johnson and Daniël Paulusma,
Kempe equivalence of colourings of cubic graphs,
European Journal of Combinatorics 59, pp. 1-10, 2017. (LINK)

[60]
Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou,
Parameterized complexity of the list coloring reconfiguration problem with graph parameters,
arXiv 1705.07551, 2017. (LINK)

[61]
Duc A. Hoang, Eli Fox-Epstein and Ryuhei Uehara,
Sliding tokens on block graphs,
Proceedings of the 11th International Workshop on Algorithms and Computation (WALCOM 2017), Lecture Notes in Computer Science 10167, pp. 460-471, 2017. (LINK)

[62]
Duc A. Hoang and Ryuhei Uehara,
Polynomial-time algorithms for sliding tokens on cactus graphs and block graphs,
arXiv 1705.00429, 2017. (LINK)

[63]
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto,
Reconfiguration of maximum-weight b-matchings in a graph,
Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), Lecture Notes in Computer Science 10392, pp. 287-296, 2017. (LINK)

[64]
Daniel Lokshtanov and Amer E. Mouawad,
The complexity of independent set reconfiguration on bipartite graphs,
arXiv 1707.02638, 2017. (LINK)

[65]
Haruka Mizuta, Takehiro Ito and Xiao Zhou,
Reconfiguration of Steiner trees in an unweighted graph,
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100-A(7), pp. 1532-1540, 2017. (LINK)

[66]
Amer E. Mouawad, Naomi Nishimura, Vinayak Pathak and Venkatesh Raman,
Shortest reconfiguration paths in the solution space of Boolean formulas,
SIAM Journal on Discrete Mathematics 31(3), pp. 2185-2200, 2017. (LINK)

[67]
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour and Akira Suzuki,
On the parameterized complexity of reconfiguration problems,
Algorithmica 78(1), pp. 274-297, 2017. (LINK)

[68]
Hiroki Osawa, Akira Suzuki, Takehiro Ito and Xiao Zhou,
The complexity of (list) edge-coloring reconfiguration problem,
Proceedings of the 11th International Workshop on Algorithms and Computation (WALCOM 2017), Lecture Notes in Computer Science 10167, pp. 347-358, 2017. (LINK)

[69]
Marthe Bonamy and Nicolas Bousquet,
Token sliding on chordal graphs,
Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), Lecture Notes in Computer Science, to appear.