Wyszukiwarka
Abstrakt
Rozważamy następujący problem obliczeniowy. Agent zostaje umieszczony w wierzchołku nieznanego mu grafu. Wierzchołki grafu są nierozróżnialne, natomiast krawędzie posiadają numery portów. Zadaniem agenta jest wyznaczenie mapy, tzn. obliczenie izomorficznej kopii grafu, lub obliczenie dowolnego drzewa spinającego grafu. Bez dodatkowej informacji zadań tych nie można wykonać. W artykule wyznaczamy oszacowania na minimalną liczbę bitów informacji jaką agent musi otrzymać, aby rozwiązać powyższe zadanie. Oszacowanie jest asymptotycznie dokładne w przypadku pierwszego z zadań, oraz asymptotycznie 'prawie' dokładne w przypadku drugiego zadania.
Cytowania
-
3 4
CrossRef
-
0
Web of Science
-
3 7
Scopus
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
nr 72,
strony 132 - 143,
ISSN: 0743-7315 - Język:
- angielski
- Rok wydania:
- 2012
- Opis bibliograficzny:
- Dereniowski D., Pelc A.: Drawing maps with advice// JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. -Vol. 72, nr. iss. 2 (2012), s.132-143
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.jpdc.2011.10.004
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 143 razy