6 papers
Algorithms and hardness for Metric Dimension on digraphs
Antoine Dailly, Florent Foucaud, Anni Hakanen
In the Metric Dimension problem, one asks for a minimum-size set of vertices such that for any pair of vertices of the graph, there is a vertex from whose two distances to…
Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles
Kyle Burke, Antoine Dailly, Nacim Oijid
Arc-Kayles is a game where two players alternate removing two adjacent vertices until no move is left, the winner being the player who played the last move. Introduced in 1978, its…
Largest planar graphs of diameter and fixed maximum degree -- connection with fractional matchings
Antoine Dailly, Sasha Darmon, Ugo Giocanti +2
The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree and diameter . In this paper, we focus on planar graphs of diamete…
The Closed Geodetic Game: algorithms and strategies
Antoine Dailly, Harmender Gahlawat, Zin Mar Myint
The geodetic closure of a set S of vertices of a graph is the set of all vertices in shortest paths between pairs of vertices of S. A set S of vertices in a graph is geodetic if it…
The Canadian Traveller Problem on outerplanar graphs
Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev +5
We study the -Canadian Traveller Problem, where a weighted graph with a source and a target are given. This problem also has a hidden input $E_* \…
Resolving Sets in Temporal Graphs
Jan Bok, Antoine Dailly, Tuomo Lehtilä
A \emph{resolving set} in a graph is a set of vertices such that every vertex of is uniquely identified by its distances to the vertices of . Introduced in the 1970s…