More applications of the d-neighbor equivalence: acyclicity and connectivity constraints

Benjamin Bergougnoux, Mamadou Moustapha Kanté

In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Nod…