3 papers
cs.DS2020
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell +1
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time , for F…
cs.DS2018
Counting Minimal Transversals of -Acyclic Hypergraphs
Benjamin Bergougnoux, Florent Capelli, Mamadou Moustapha Kanté
We prove that one can count in polynomial time the number of minimal transversals of -acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal…
cs.DS2018
On Minimum Connecting Transition Sets in Graphs
Thomas Bellitto, Benjamin Bergougnoux
A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the g…