Wyszukiwarka
Abstrakt
Rozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto wykazano, że w przypadku ogólnym żaden algorytm on-line nie może mieć współczynnika aproksymacji mniejszego niż (2 − epsilon), dla dowolnego epsilon > 0. Dla szczególnego przypadku, w którym liczba ścieżek jest liniowa względem liczby wierzchołków grafu, podano wielomianowy algorytm off-line znajdujący dokładne rozwiązanie problemu oraz wykazano, że żaden algorytm on-line nie może mieć współczynnika aproksymacji mniejszego niż (1.5 − epsilon). Zaproponowane techniki algorytmiczne zaadaptowano również do rozwiązania innych problemów w grafach pełnych, m.in. problemu routingu optycznego oraz routingu z ograniczonym obciążeniem krawędziowym.
Cytowania
-
4
CrossRef
-
0
Web of Science
-
4
Scopus
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2008.02.017
- Licencja
- Copyright (2008 Elsevier B.V.)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie z listy filadelfijskiej
- Opublikowano w:
-
THEORETICAL COMPUTER SCIENCE
nr 399,
strony 128 - 140,
ISSN: 0304-3975 - Język:
- angielski
- Rok wydania:
- 2008
- Opis bibliograficzny:
- Kosowski A.: The maximum edge-disjoint paths problem in complete graphs// THEORETICAL COMPUTER SCIENCE. -Vol. 399., nr. nr 1-2 (2008), s.128-140
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2008.02.017
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 90 razy
Publikacje, które mogą cię zainteresować
Universal Augmentation Schemes for Network Navigability
- P. Fraigniaud,
- C. Gavoille,
- A. Kosowski
- + 2 autorów