Skip to Main content Skip to Navigation
New interface
Journal articles

Distinguishing Views in Symmetric Networks: A Tight Lower Bound

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\geq D\geq 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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00875370
Contributor : Adrian Kosowski Connect in order to contact the contributor
Submitted on : Sunday, March 8, 2015 - 2:50:37 PM
Last modification on : Friday, January 21, 2022 - 3:15:14 AM
Long-term archiving on: : Monday, April 17, 2017 - 4:08:17 AM

Files

view.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak. Distinguishing Views in Symmetric Networks: A Tight Lower Bound. Theoretical Computer Science, 2015, 582, pp.27-34. ⟨10.1016/j.tcs.2015.03.018⟩. ⟨hal-00875370v3⟩

Share

Metrics

Record views

319

Files downloads

374