The problem of finding a robust spanning tree has been analysed. The problem consists of determining
a minimum spanning tree of a graph with uncertain edge costs. We should determine
a spanning tree that minimizes the difference in costs between the tree selected and the optimal tree.
While doing this, all possible realizations of the edge costs should be taken into account. This issue
belongs to the class of NP-hard problems. In this paper, an algorithm based on the cost perturbation
method and adapted to the analysed problem has been proposed. The paper also contains the results of
numerical experiments testing the effectiveness of the proposed algorithm and compares it with algorithms
known in the literature. The research is based on a large number of various test examples taken
from the literature.
Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00