Skip to Main content Skip to Navigation
Journal articles

Distinguishing Views in Symmetric Networks: A Tight Lower Bound

Dariusz Dereniowski 1 Adrian Kosowski 2 Dominik Pajak 3
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
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 metadatas
Contributor : Adrian Kosowski <>
Submitted on : Sunday, March 8, 2015 - 2:50:37 PM
Last modification on : Friday, March 27, 2020 - 3:00:48 AM
Document(s) archivé(s) le : Monday, April 17, 2017 - 4:08:17 AM


Files produced by the author(s)




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



Record views


Files downloads