2 citations · 3 across the 5 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2023★ 1 cited
Cutting Barnette graphs perfectly is hard
Édouard Bonnet, Dibyayan Chakraborty, Julien Duron
A perfect matching cut is a perfect matching that is also a cutset, or equivalently a perfect matching containing an even number of edges on every cycle. The corresponding algorith…
cs.CC2014
Havannah and TwixT are PSPACE-complete
Edouard Bonnet, Florian Jamain, Abdallah Saffidine
Numerous popular abstract strategy games ranging from Hex and Havannah to Lines of Action belong to the class of connection games. Still, very few complexity results on such games…