Header menu link for other important links
Tree topology inference from leaf-to-leaf path lengths using Prüfer sequence
Kamala Krithivasan
Published in Inderscience Publishers
Volume: 12
Issue: 2
Pages: 225 - 237
In this paper, we propose an algorithm to reconstruct the set of nodes and their topology relationships, particularly in case of a topological tree (where all edge weights are 1), given the set of terminal vertices or leaves and their pairwise distances or path lengths. Prüfer encoding and decoding techniques showed a one-to-one correspondence between n-labelled trees and (n - 2)-tuples of vertex labels. We consider Prüfer encoding technique in discovering the intermediate vertices from the end-to-end path length between all pairs of terminal vertices. The results are useful in inferring graph characteristics, topology in particular, in the field of network tomography where the internal structure and link-level performance are inferred from end-to-end measurements. Copyright © 2014 Inderscience Enterprises Ltd.
About the journal
JournalInternational Journal of Communication Networks and Distributed Systems
PublisherInderscience Publishers
Open AccessNo
Concepts (11)
  •  related image
  •  related image
    Encoding (symbols)
  •  related image
  •  related image
    Distance matrices
  •  related image
  •  related image
    Network tomography
  •  related image
  •  related image
    Topology inference
  •  related image
  •  related image
  •  related image
    Trees (mathematics)