Distinguishing views in symmetric networks: A tight lower bound - Publikacja - MOST Wiedzy

Wyszukiwarka

Distinguishing views in symmetric networks: A tight lower bound

Abstrakt

The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers n ≥ D ≥ 1, there exists a port-labeled network with at most n nodes and diameter at most D which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth Omega( D log(n/ D )) are identical.

Cytowania

  • 3

    CrossRef

  • 3

    Web of Science

  • 3

    Scopus

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
THEORETICAL COMPUTER SCIENCE nr 582, strony 27 - 34,
ISSN: 0304-3975
Język:
angielski
Rok wydania:
2015
Opis bibliograficzny:
Dereniowski D., Kosowski A., Pająk .: Distinguishing views in symmetric networks: A tight lower bound// THEORETICAL COMPUTER SCIENCE. -Vol. 582, (2015), s.27-34
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2015.03.018
Weryfikacja:
Politechnika Gdańska

wyświetlono 17 razy

Publikacje, które mogą cię zainteresować

Meta Tagi