Search
Abstract
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.
Citations
-
4
CrossRef
-
0
Web of Science
-
5
Scopus
Authors (3)
-
-
Dominik Pająk
- University of Cambridge, United Kingdom Computer Laboratory
Cite as
Full text
download paper
downloaded 28 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2015.03.018
- License
- Copyright (2015 Elsevier B.V)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
THEORETICAL COMPUTER SCIENCE
no. 582,
pages 27 - 34,
ISSN: 0304-3975 - Language:
- English
- Publication year:
- 2015
- Bibliographic description:
- 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:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2015.03.018
- Verified by:
- Gdańsk University of Technology
seen 145 times