Ważone umieszczanie grafów jako model optymalizacji komunikacji w sieciach heterogenicznych

• Autorzy: Bruniecki K.

Warianty tytułu

EN

Weighted graph embedding for modeling communication costs in heterogenous networks

• Języki publikacji: PL

Abstrakty

PL

Umieszczenie grafu w grafie jest odwzorowaniem pomiędzy parą grafów. Graf umieszczany reprezentuje sieć komunikujących się ze sobą zadań, natomiast graf docelowy - dostępną architekturę wykonania tych zadań. Problem polega na takim odwzorowaniu wierzchołków i krawędzi, aby zminimalizować koszty wynikające z potrzeby użycia zastępczych ścieżek w grafie docelowym. W klasycznym modelu przyjmuje się, że oba grafy są proste i ich krawędzie są nierozróżnialne. W pracy zaproponowane zostało uogólnienie modelu klasycznego. Uogólnienie polega na zróżnicowaniu krawędzi grafów za pomocą funkcji wagowej o interpretacji odległościowej. W kontekście takiego modelu ważonego zostają przedstawione algorytmy umieszczania pewnych acyklicznych grafów, zwanych pająkami, w dowolnych grafach.

EN

Embedding a graph into another graph is a mapping between two graphs. A guest graph represents network of communicating tasks and a host graph model s a destination architecture. The aim is to construct such a mapping that the lengths of paths in the host graph representing edges from guest graph, are the shortest possible. In this paper we propose a weighted generalization of the classical model. Also, there are presented algorithms for the problem of embedding spider graphs into graphs in this weighted model.

Słowa kluczowe

PL

umieszczenie grafu w grafie; komunikacja w sieciach heterogenicznych

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2008
• Tom: T. 16
• Strony: 403--408
• Opis fizyczny: Bibliogr. 6 poz., rys., tab.

Twórcy

autor

Bruniecki K.

• Politechnika Gdańska, Katedra Algorytmów i Modelowania Systemów

Bibliografia

• [1] Monien B., Sudborough I. H.: Embedding one interconnection network in another. Computing Supplementum, s. 257-282, nr 7, 1990.
• [2] Harper L. H.: Optimal assignments on numbers to vertices. SIAM Journal, s.131-135, nr 12, 1964.
• [3] Chvatalova J.: Optimal labelling of a product of two paths. Discrete Mathematics, s. 249-253, nr II, 1975.
• [4] Papadimitriou C. H.: The NP-completeness of the bandwidth minimization problem. Computing, 263-270, nr 16, 1976.
• [5] Micali S., Vazirani V.: An O(|V|1/2|E|) algorithm for finding maximum matching in general graphs. W: Proceedings of 21st Annual Symposium Foundations of Computer Science, 1980, New York, USA, s.17-27.
• [6] Kirkpatrick D. G., Hen P.: On the completeness of a generalized matching problem. W: Proceedings of the tenth annual ACM symposium on Theory of computing, STOC '78, 1978, New York, USA s.240-245.