Given an n-vertex and m-edge non-negatively real-weighted graph G = (V,E,w), whose vertices are partitioned into a set of k clusters, a clustered network design problem on G consists of finding a (possibly optimal) solution to a given network design problem on G, subject to some additional constraint on its clusters. In this paper, we focus on the classic shortest-path tree problem and summarize our ongoing work in this field. In particular, we analyze the hardness of a clustered version of the problem in which the additional feasibility constraint consists of forcing each cluster to form a (connected) subtree.
|Titolo:||On the clustered shortest-path tree problem|
|Autori interni:||D'EMIDIO, MATTIA|
|Data di pubblicazione:||2016|
|Rivista:||CEUR WORKSHOP PROCEEDINGS|
|Appare nelle tipologie:||4.1 Contributo in Atti di convegno|