Hardness, Approximability, and Fixed-Parameter Tractability of the Clustered Shortest-Path Tree Problem

Mattia D'Emidio, Luca Forlizzi, Daniele Frigioni +2

Given an $n$-vertex non-negatively real-weighted graph $G$, whose vertices are partitioned into a set of $k$ clusters, a \emph{clustered network design problem} on $G$ consists of…