22 citations · 66 across the 34 of their papers we have counts for
59 papers
Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
Gaétan Berthe, Florent Foucaud, Tuomo Lehtilä +1
The neighbourhood complexity of a graph is a quantity measuring, for a graph and an integer , the maximum possible number (over all vertex subsets of size…
Algorithms and complexity for geodetic sets on interval and chordal graphs
Dibyayan Chakraborty, Sandip Das, Florent Foucaud +2
We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set of vertices of a graph is a \textit{geodetic se…
Structural parameterizations of Geodetic Set on directed (acyclic) graphs
Laurent Beaudou, Florent Foucaud, Lucas Lorieau +1
In DIRECTED GEODETIC SET, we are given a (directed) graph and seek a small solution set such that every vertex lies on a shortest directed path between two verti…
Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
Florent Foucaud, Narges Ghareghani, Lucas Lorieau +3
In the GEODETIC SET problem, an input is a (di)graph and integer , and the objective is to decide whether there exists a vertex subset of size such that any vertex i…
Locating-dominating coalitions in graphs
M. Chellali, A. A. Dobrynin, F. Foucaud +2
A set of vertices in a graph is a locating-dominating set (LD-set) if it is dominating and every two vertices , of satisfy $N(u) \cap D \neq…
Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
Florent Foucaud, Atrayee Majumder, Tobias Mömke +1
In the PATH COVER problem, one asks to cover the vertices of a graph using the smallest possible number of (not necessarily disjoint) paths. While the variant where the paths need…