The Parameterized Hardness of the k-Center Problem in Transportation Networks

Andreas Emil Feldmann, Daniel Marx

In this paper we study the hardness of the $k$-Center problem on inputs that model transportation networks. For the problem, a graph $G=(V,E)$ with edge lengths and an integer $k$…