Search
Abstract
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.
Citations
-
1 2
CrossRef
-
0
Web of Science
-
2 0
Scopus
Authors (5)
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1145/1248377.1248379
- License
- Copyright (2009 Elsevier B.V)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
THEORETICAL COMPUTER SCIENCE
no. 410,
pages 1970 - 1981,
ISSN: 0304-3975 - Language:
- English
- Publication year:
- 2009
- Bibliographic description:
- 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:
- Digital Object Identifier (open in new tab) 10.1145/1248377.1248379
- Verified by:
- Gdańsk University of Technology
seen 112 times
Recommended for you
On the complexity of distributed graph coloring with local minimality constraints
- C. Gavoille,
- R. Klasing,
- A. Kosowski
- + 2 authors