List of some publications related to "Combinatorial Reconfiguration"
Posted by Duc A HoangDuc A Hoang on 10 Feb 2019 07:01, last edited by Duc A HoangDuc A Hoang on 03 Jul 2019 05:15

This page contains a non-exhaustive list of publications related to Combinatorial Reconfiguration, a research area in Computer Science. The publications are categorized by year. Everyone can edit this site by becoming a member. (See all members of this site.)

Extra Materials


  • Alexandre Blanché, Haruka Mizuta, Paul Ouvrard and Akira Suzuki. Decremental Optimization of Dominating Sets Under Reachability Constraints. (Preprint: arXiv:1906.05163).
  • Carl Feghali. Reconfiguring colourings of graphs with bounded maximum average degree. (Preprint: arXiv:1904.12698).
  • Ahmad Biniaz, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec and Alexi Turcotte. Token Swapping on Trees. (Preprint: arXiv:1903.06981).
  • Hugo A. Akitaya, Matthew D. Jones, Matias Korman, Christopher Meierfrankenfeld, Michael J. Munje, Diane L. Souvaine, Michael Thramann and Csaba D. Tóth. Reconfiguration of Connected Graph Partitions. (Preprint: arXiv:1902.10765).
  • Carl Feghali and Jiří Fiala. Reconfiguration Graph for Vertex Colourings of Weakly Chordal Graphs. (Preprint: arXiv:1902.08071).
  • Carl Feghali. Reconfiguring $10$-colourings of planar graphs. (Preprint: arXiv:1902.02278).

  • Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto. Shortest reconfiguration of perfect matchings via alternating cycles, Proceedings of ESA 2019.
  • Rahnuma Islam Nishat and Sue Whitesides. Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs. Proceedings of WG 2019.
  • Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito and Moritz Mühlenthaler. Shortest Reconfiguration of Matchings, Proceedings of WG 2019. (Preprint: arXiv:1812.05419).
  • Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono and Yota Otachi. Independent Set Reconfiguration Parameterized by Modular-Width, Proceedings of WG 2019. (Preprint: arXiv:1905.00340).
  • Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi and Florian Sikora. Token Sliding on Split Graphs, Proceedings of STACS 2019, LIPIcs 126, pp. 13:1-13:7 (Preprint: arXiv:1807.05322).
  • Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou. Reconfiguration of Minimum Steiner Trees via Vertex Exchanges, Proceedings of MFCS 2019.
  • Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler and Kunihiro Wasa. The Perfect Matching Reconfiguration Problem, Proceedings of MFCS 2019 (Preprint: arXiv:1904.06184).
  • Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno. Reconfiguring Undirected Paths, Proceedings of WADS 2019 (Preprint: arXiv:1905.00518).
  • Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Muehlenthaler, Akira Suzuki and Kunihiro Wasa. Diameter of Colorings Under Kempe Changes, Proceedings of COCOON 2019.
  • Takehiro Ito, Haruka Mizuta, Naomi Nishimura and Akira Suzuki. Incremental Optimization of Independent Sets under Reachability Constraints, Proceedings of COCOON 2019. (Preprint: arXiv:1804.09422).
  • Duc A. Hoang, Amanj Khorramian and Ryuhei Uehara. Shortest Reconfiguration Sequence for Sliding Tokens on Spiders, Proceedings of CIAC 2019, LNCS 11485, pp. 262-273. (Preprint: arXiv:1806.08291).
  • Carl Feghali. Paths between colourings of graphs with bounded tree-width. Information Processing Letters, 144 (2019), pp. 37-38, April 2019.
  • Manoj Gupta, Hitesh Kumar and Neeldhara Misra. On the Complexity of Optimal Matching Reconfiguration, Proceedings of SOFSEM 2019, LNCS 11376, pp. 221-233.


  • Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou. Complexity of Reconfiguration Problems for Constraint Satisfaction. (Preprint: arXiv:1812.10629).
  • Marthe Bonamy, Nicolas Bousquet and Guillem Perarnau. Frozen $(\Delta+1)$-colourings of bounded degree graphs. (Preprint: arXiv:1811.12650).
  • Keren Censor-Hillel and Mikaël Rabie. Distributed Reconfiguration of Maximal Independent Sets. (Preprint: arXiv:1810.02106).
  • Eduard Eiben and Carl Feghali. Towards Cereceda's conjecture for planar graphs. (Preprint: arXiv:1810.00731).
  • Matt DeVos, Adam Dyck, Jonathan Jedwab and Samuel Simon. Which graphs occur as $\gamma$-graphs? (Preprint: arXiv:1810.01583).
  • Jae-Baek Lee, Jonathan A. Noel and Mark Siggers. Reconfiguring Graph Homomorphisms on the Sphere. (Preprint: arXiv:1810.01111).
  • John Asplund and Brett Werner. Classification of Reconfiguration Graphs of Shortest Path Graphs With No Induced $4$-cycles. (Preprint: arXiv:1808.09387).
  • Michael Anastos and Alan Frieze. On the connectivity threshold for colorings of random graphs and hypergraphs. (Preprint: arXiv:1803.05246).


  • Richard C. Brewster, Jae-Baek Lee, Benjamin Moore, Jonathan A. Noel and Mark Siggers. Graph Homomorphism Reconfiguration and Frozen $H$-Colourings. (Preprint: arXiv:1712.00200).


  • Anna Lubiw, Vinayak Pathak. Reconfiguring Ordered Bases of a Matroid. (Preprint: arXiv:1612.00958).


  • Daniel C. McDonald. Connectedness and Hamiltonicity of graphs on vertex colorings. (Preprint: arXiv:1507.05344).


  • Marthe Bonamy and Nicolas Bousquet. Reconfiguring Independent Sets in Cographs. (Preprint: arXiv:1406.1433).





  • Somkiat Trakultraipruk. Connectedness of Strong $k$-Colour Graphs. (Preprint: arXiv:1009.4440).





  • Bojan Mohar. Kempe Equivalence of Colorings, Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge, pp. 287-297. Trends in Mathematics. Birkhäuser Basel.




  • Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan and Hisao Tamaki. Motion planning on a graph. Proceedings of SFCS 1994, pp. 511-520, IEEE.


File nameFile typeSize
core.bibASCII English text76.14 kBInfo
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License