Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: umieszczenie grafu w grafie

Sortuj według:

Ogranicz wyniki do:

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

Bruniecki K.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

2008

T. 16

403-408

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.

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.