The minimum routing cost tree problem arises when we need to find the tree minimizing the minimum travel/communication cost, i.e., the tree which presents the minimal difference with the same cost computed on the whole network. This paper provides the state of the art of the problem and proposes a new heuristic based on the identification of a core of the network around which the solution can be built. The algorithm has been tested on literature instances of up to one thousand nodes. The results, compared with those of other heuristic algorithms, prove the competitiveness of the proposed one both in terms of the quality of the solution and computation time.

The Minimum Routing Cost Tree Problem State of the art and a core-node based heuristic algorithm / Masone, Adriano; Nenni, MARIA ELENA; Sforza, Antonio; Sterle, Claudio. - In: SOFT COMPUTING. - ISSN 1432-7643. - 23:9(2019), pp. 2947-2957. [10.1007/s00500-018-3557-3]

The Minimum Routing Cost Tree Problem State of the art and a core-node based heuristic algorithm

Masone Adriano;Nenni Maria Elena;Sforza Antonio;Sterle Claudio
2019

Abstract

The minimum routing cost tree problem arises when we need to find the tree minimizing the minimum travel/communication cost, i.e., the tree which presents the minimal difference with the same cost computed on the whole network. This paper provides the state of the art of the problem and proposes a new heuristic based on the identification of a core of the network around which the solution can be built. The algorithm has been tested on literature instances of up to one thousand nodes. The results, compared with those of other heuristic algorithms, prove the competitiveness of the proposed one both in terms of the quality of the solution and computation time.
2019
The Minimum Routing Cost Tree Problem State of the art and a core-node based heuristic algorithm / Masone, Adriano; Nenni, MARIA ELENA; Sforza, Antonio; Sterle, Claudio. - In: SOFT COMPUTING. - ISSN 1432-7643. - 23:9(2019), pp. 2947-2957. [10.1007/s00500-018-3557-3]
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/11588/723653
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact