Distinguishing Views in Symmetric Networks: A Tight Lower Bound - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

Distinguishing Views in Symmetric Networks: A Tight Lower Bound

Résumé

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.
Fichier principal
Vignette du fichier
view.pdf (239.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00875370 , version 1 (21-10-2013)
hal-00875370 , version 2 (15-05-2014)
hal-00875370 , version 3 (08-03-2015)

Identifiants

  • HAL Id : hal-00875370 , version 1

Citer

Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak. Distinguishing Views in Symmetric Networks: A Tight Lower Bound. 2013. ⟨hal-00875370v1⟩
326 Consultations
390 Téléchargements

Partager

Gmail Facebook X LinkedIn More