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.
Authors
- Pierre Fraigniaud,
- Cyril Gavoille,
- dr inż. Adrian Kosowski link open in new tab ,
- Emmanuelle Lebhar,
- Zvi Lotker
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1145/1248377.1248379
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2009
