Drawing maps with advice - Publikacja - MOST Wiedzy

Wyszukiwarka

Drawing maps with advice

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 3

    CrossRef

  • 0

    Web of Science

  • 3 6

    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 100 razy

Publikacje, które mogą cię zainteresować

Meta Tagi