14 citations · 34 across the 9 of their papers we have counts for
3 papers · 1 filter
Complexity Dichotomies for the Minimum F-Overlay Problem
Nathann Cohen, Frédéric Havet, Dorian Mazauric +2
For a (possibly infinite) fixed family of graphs F, we say that a graph G overlays F on a hypergraph H if V(H) is equal to V(G) and the subgraph of G induced by every hyperedge of…
A Polynomial-time Algorithm for Outerplanar Diameter Improvement
Nathann Cohen, Daniel Gonçalves, Eun Jung Kim +4
The Outerplanar Diameter Improvement problem asks, given a graph and an integer , whether it is possible to add edges to in a way that the resulting graph is outerplanar…
Algorithm for Finding -Vertex Out-trees and its Application to -Internal Out-branching Problem
Nathann Cohen, Fedor V. Fomin, Gregory Gutin +3
An out-tree is an oriented tree with only one vertex of in-degree zero. A vertex of is internal if its out-degree is positive. We design randomized and deterministic al…