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.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1016/j.jpdc.2011.10.004
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie wyróżnionym w JCR
- Język
- angielski
- Rok wydania
- 2012
Źródło danych: MOSTWiedzy.pl - publikacja "Drawing maps with advice" link otwiera się w nowej karcie
