Algorytm poszukiwania z zabronieniami dla problemu centralnego drzewa rozpinającego

Abstract

W pracy analizuje się problem znajdowania centralnego drzewa rozpinającego. Problem ten polega na znalezieniu takiego drzewa rozpinającego graf, aby największa odległość od wszystkich pozostałych drzew była możliwie najmniejsza. Odległość pomiędzy drzewami jest miarą zliczającą różnice w zbiorze krawędzi porównywanych drzew. Zagadnienie to należy do klasy problemów NP-trudnych. W pracy proponuje się algorytm, oparty na metodzie poszukiwania z zabronieniami, dedykowany rozpatrywanemu problemowi. Praca zawiera także wyniki eksperymentów numerycznych testujących efektywność proponowanego algorytmu oraz porównuje go z algorytmem dokładnym opartym na metodzie podziału i ograniczeń.

In this paper the central spanning tree problem is considered. The problem consists in finding a spanning tree in a graph, that minimizes the maximum distance to all other spanning trees. The distance between two trees is measured by means of the symmetric difference of their edge sets. The problem is known to be NP-hard. The algorithm based on the tabu search approach is proposed. Computational experiments are conducted and compared with results obtained by a branch and bound algorithm.