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ść
- 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)
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ć
On the complexity of distributed graph coloring with local minimality constraints
- C. Gavoille,
- R. Klasing,
- A. Kosowski
- + 2 autorów