Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii

摘要

Let G = (V, E) denote a weighted graph of n nodes and m edges, and let G[V'] denote the subgraph of G induced by a subset of nodes V' is contained in V. The radius of G[V'] is the maximum length of a shortest path in G[V'] emanating from its center (i.e., a node of G[V'] of minimum eccentricity). In this paper, we focus on the problem of partitioning the nodes of G into exactly p non-empty subsets, so as to minimize the sum of the induced subgraph radii. We show that this problem - which is of significance in facility location applications - is NP-hard when p is part of the input, but for a fixed constant p ＞ 2 it can be solved in O(n~(2p)/p!) time. Moreover, for the notable case p = 2, we present an efficient O(mn~2 + n~3 log n) time algorithm.