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.

On the clustered shortest-path tree problem

D'EMIDIO, MATTIA;FORLIZZI, LUCA;FRIGIONI, DANIELE;LEUCCI, STEFANO;PROIETTI, GUIDO
2016-01-01

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/109048
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? ND
social impact