Wyszukiwarka
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
-
4
CrossRef
-
0
Web of Science
-
5
Scopus
Autorzy (3)
-
-
Dominik Pająk
- University of Cambridge, United Kingdom Computer Laboratory
Cytuj jako
Pełna treść
pobierz publikację
pobrano 25 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2015.03.018
- Licencja
- Copyright (2015 Elsevier B.V)
Słowa kluczowe
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 137 razy