Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
Davide Bilò, Giordano Colli, Luca Forlizzi +1
We study the minimum \emph{Monitoring Edge Geodetic Set} (\megset) problem introduced in [Foucaud et al., CALDAM'23]: given a graph , we say that an edge is monitored by a pair…
cs.DS2018
Hardness, Approximability, and Fixed-Parameter Tractability of the Clustered Shortest-Path Tree Problem
Mattia D'Emidio, Luca Forlizzi, Daniele Frigioni +2
Given an -vertex non-negatively real-weighted graph , whose vertices are partitioned into a set of clusters, a \emph{clustered network design problem} on consists of…