Drawing maps with advice

Dariusz Dereniowski; Andrzej Pelc

doi:10.1016/j.jpdc.2011.10.004

Drawing maps with advice

Abstract

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.

Citations

3 4

CrossRef
0

Web of Science
3 7

Scopus

Authors (2)

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING no. 72, pages 132 - 143,
ISSN: 0743-7315
Language:: English
Publication year:: 2012
Bibliographic description:: Dereniowski D., Pelc A.: Drawing maps with advice// JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. -Vol. 72, nr. iss. 2 (2012), s.132-143
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.jpdc.2011.10.004
Verified by:: Gdańsk University of Technology