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

Abstract

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

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