Distinguishing Views in Symmetric Networks: A Tight Lower Bound

Dariusz Dereniowski (1) , Adrian Kosowski (2) , Dominik Pajak (3)

1 Gdansk University of Technology - Department of Algorithms and Systems Modelling [ETI GUT]
2 GANG - Networks, Graphs and Algorithms
3 Computer Laboratory [Cambridge]

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.

Domaines: Algorithme et structure de données [cs.DS]

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⟩