Porównanie algorytmów ważonego umieszczania grafów w grafach minimalizujących opóźnienia komunikacyjne

• Autorzy: Bruniecki K.

Warianty tytułu

EN

Comparison of algorithms for weighted graph into graph embedding problem with minimization of communication delays

• Języki publikacji: PL

Abstrakty

PL

W artykule omówiono i porównano zaimplementowane algorytmy ważonego umieszczania grafów w grafach. Z uwagi na obliczeniową trudność problemu ogólnego większość przedstawionych podejść to heurystyki. Dla ograniczonych instancji problemu zaproponowano podejście dokładne oparte na idei backtrackingu. W pracy zawarto porównanie algorytmów pod względem czasów działania i jakości uzyskanych rozwiązań. Algorytmy zaimplementowane zostały w języku C++.

EN

This paper discusses different algorithms implemented for graph into graph embedding problem. Due to computational complexity hardness, some of presented algorithms are based on heuristic approach. For limited graphs instances exact algorithms with an idea of backtracking are proposed. Comparison between presented algorithms, in aspects of time and the quality of obtained solutions is presented. Presented algorithms have been implemented in C++.

Słowa kluczowe

PL

umieszczanie grafów w grafach; dylatacja ważona; backtracking

EN

graph into graph embedding; weighted dilation; backtracking

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 223--230
• Opis fizyczny: Bibliogr. 6 poz., rys., tab.

Twórcy

autor

Bruniecki K.

• Katedra Systemów Geoinformatycznych, Politechnika Gdańska

Bibliografia

• [1] Monien В., Sudborough I.H., Embedding one interconnection network in another. Computing Supplementum, nr 7, 1990, 257-282.
• [2] Harper L.H., Optimal assignments on numbers to vertices. SIAM Journal, nr 12, 1964, 131-135.
• [3] Chvatalova J., Optimal labelling of a product of two paths. Discrete Mathematics, nr 11, 1975, 249-253.
• [4] Papadimitriou C.H., The NF'-completeness of the bandwidth minimization problem. Computing, nr 16, 1976, 263-270.
• [5] Bruniecki K., Modele umieszczania grafów w grafach i ich zastosowania. Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej (Technologie Informacyjne), nr 13, 2007, 457-464.
• [6] Bruniecki K., Ważone umieszczanie grafów w grafach jako model optymalizacji komunikacji w sieciach heterogeniczncych. Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej (Technologie Informacyjne), nr 16, 2008, 403-08.