carpathian_2020_36_3_401_414_001

A novel genetic algorithm for solving the clustered shortest-path tree problem


 Cosma, Ovidiu, Pop, Petrică C. and Zelina, Ioana 


Abstract

carpathian_2020_36_3_401_414_abstract

The clustered shortest-path tree problem is an extension of the classical single-source shortest-path problem, in which, given a graph with the set of nodes divided into a predefined, mutually exclusive and exhaustive set of clusters, we want to determine a shortest-path spanning tree from a given source to all the other nodes of the graph, with the property that each cluster should induce a connected subtree. The investigated problem proved to be NP-hard and therefore we proposed an efficient genetic algorithm in order to solve it. The preliminary computational results reported on a set of benchmark instances from the literature proved that our proposed solution approach yields high-quality solutions within reasonable running times.

Additional Information

Author(s)

 Cosma, Ovidiu, Pop, Petrică C., Zelina, Ioana