Universal Augmentation Schemes for Network Navigability

Pierre Fraigniaud; Cyril Gavoille; Adrian Kosowski; Emmanuelle Lebhar; Zvi Lotker

doi:10.1145/1248377.1248379

Universal Augmentation Schemes for Network Navigability

Abstrakt

Rozważano problem uzupełniania grafu (reprezentującego np. sieci społeczne) poprzez dodanie w każdym węźle jednego dodatkowego skierowanego połączenia (długodystansowego). Dokładniej, dla każdego węzła definiuje się listę prawdopodobieństw istnienia połączenia wychodzącego z danego węzła do wszystkich pozostałych węzłów; wartości tych prawdopodobieństw muszą sumować się do jedności. Routing zachłanny w takiej sieci polega na przekazywaniu informacji od węzła źródłowego do docelowego, w taki sposób, że każdy węzeł przekazuje informacje do węzła najbliższego węzłowi docelowemu (nie znając przy tym konfiguracji połączeń długodystansowych innych węzłów). W pracy podano pierwszy ogólny algorytm definiowania struktury połączeń długodystansowych, tak aby zagwarantować oczekiwany czas routingu poniżej O(sqrt(n)) (dokładniej O(n^{1/3} * poly(log n))) dla każdej pary węzłów. Zaproponowano także algorytmy dla innych wariantów problemu.

Cytowania

1 2

CrossRef
0

Web of Science
2 0

Scopus

Autorzy (5)

Cytuj jako

Pełna treść

pobierz publikację

pobrano 14 razy

Wersja publikacji: Accepted albo Published Version
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1145/1248377.1248379
Licencja: Copyright (2009 Elsevier B.V)

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: THEORETICAL COMPUTER SCIENCE nr 410, strony 1970 - 1981,
ISSN: 0304-3975
Język:: angielski
Rok wydania:: 2009
Opis bibliograficzny:: Fraigniaud P., Gavoille C., Kosowski A., Lebhar E., Lotker Z.: Universal Augmentation Schemes for Network Navigability// THEORETICAL COMPUTER SCIENCE. -Vol. 410, nr. iss. 21-23, May. (2009), s.1970-1981
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1145/1248377.1248379
Weryfikacja:: Politechnika Gdańska