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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2015, 582, pp.27-34. 〈10.1016/j.tcs.2015.03.018〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00875370
Contributeur : Adrian Kosowski <>
Soumis le : dimanche 8 mars 2015 - 14:50:37
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : lundi 17 avril 2017 - 04:08:17

Fichiers

view.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

187

Téléchargements de fichiers

226