Web Survey on Combinatorial Reconfiguration

(back to home) (about this survey)

Filters:
Problems: Satisfiability
Choose Problem

Authors: all
Choose Author


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

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

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

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