Universal Augmentation Schemes for Network Navigability - Publikacja - MOST Wiedzy

Wyszukiwarka

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

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

wyświetlono 106 razy

Publikacje, które mogą cię zainteresować

Meta Tagi