The hop-constrained minimum spanning tree problem is the problem of determining a rooted spanning tree of minimum cost in which each path from the root node to any other node contains at most H hops or edges. This problem relates to the design of centralized tree networks with quality of service requirements (in telecommunications) and has a close relation with other tree problems. In this paper we investigate the adaptation of some well-known "repetitive" heuristics used for the capacitated minimum spanning tree problem to the hop-constrained minimum spanning tree problem and investigate some simple look ahead mechanisms for enhancing the quality of a savings heuristic. Computational results for a set of benchmark tests with up to 80 nodes are presented.
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