Web Survey on Combinatorial Reconfiguration

(back to home) (about this survey)

Filters:
Problems: Independent set
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)

[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)

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

[21]
Marthe Bonamy and Nicolas Bousquet,
Reconfiguring independent sets in cographs,
arXiv 1406.1433, 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)

[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)

[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)

[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)

[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)

[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)

[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)

[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)

[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)

[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)

[64]
Daniel Lokshtanov and Amer E. Mouawad,
The complexity of independent set reconfiguration on bipartite graphs,
arXiv 1707.02638, 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)

[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.