Algorytm poszukiwania z zabronieniami dla problemu centralnego drzewa rozpinającego

• Autorzy: Makuchowski M.

Warianty tytułu

EN

Algorithm tabu for the central spanning tree problem

• Języki publikacji: PL

Abstrakty

PL

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ń.

EN

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.

Słowa kluczowe

PL

problem centralnego drzewa rozpinającego; drzewo rozpinające; metoda poszukiwania z zabronieniami; optymalizacja odporna

EN

central spanning tree problem; spanning tree; tabu search algorithm; robust optimization

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2011
• Tom: T. 15, z. 2
• Strony: 319--326
• Opis fizyczny: Bibliogr. 11 poz., wykr., tab.

Twórcy

autor

Makuchowski M.

• Politechnika Wrocławska, Instytut Informatyki, Automatyki i Robotyki

Bibliografia

• [1] Deo N., A central tree. IEEE Transactions on Circuit Theory, vol. ct-13, 1966, 439-440.
• [2] Bezrukov S., Kaderali F., Poguntke W., On central spanning trees ofa graph. Lecture Notes Computer Science, 1120, 1996, 53-58.
• [3] Kasperski A., Zieliński R, An approximation algorrithm for interwal data minmax regret combi-natorial optimalization problems. Information Processing Letters, 97(5), 2006, 177-18.
• [4] Bang-Jensen J., Nikulin Y., Heuristics for the central tree problem. Journal of Heuristics, 16, 2010, 663-651.
• [5] Harary F., Graph theory. Addison-Wesley Publ. Company, 1969.
• [6] Aron I., Hentenryck P., On the complexity ofthe robust spanning tree problem with interval data. Operations Research Letters, 32, 2004, 36-40.
• [7] Kruskal J.B., On the shortest spanning subtree of graph and the trveling salesman problem.. KProc. Amer. Math. Soc, 7, 1956, 48-50.
• [8] Prim R.C., Shortest connection networks and some generalizations. Bell System Technical Journal, 36, 1957, 1389-1401.
• [9] Glover F., Laguna M., Tabu Search..KhssN& Academic Publishers, Massachusetts, USA, 1997.
• [10] Nowicki E., Metoda tabu w problemach szeregowania zadań produkcyjnych. Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław 1999.
• [11] Kasperski A., Discrete optimalization with interval data: Minmax regret andfuzzy approach.Sta-dies in Fuzziness and Soft Computing, vol 228. Springer-Verlag, Berlin Heidelberg 2008.