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

https://hal.inria.fr/hal-00875370
Contributor : Adrian Kosowski <>
Submitted on : Sunday, March 8, 2015 - 2:50:37 PM
Last modification on : Friday, April 12, 2019 - 10:18:09 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, Elsevier, 2015, 582, pp.27-34. ⟨10.1016/j.tcs.2015.03.018⟩. ⟨hal-00875370v3⟩

Share

Metrics

Record views

248

Files downloads

471