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.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.jpdc.2011.10.004
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2012
Source: MOSTWiedzy.pl - publication "Drawing maps with advice" link open in new tab
