Title: Tree topology inference from leaf-to-leaf path lengths using Prüfer sequence

Authors: Vanniarajan Chellappan; Kamala Krithivasan

Addresses: Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai 600036, India ' Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai 600036, India

Abstract: 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.

Keywords: graphs; topological trees; paths; network tomography; Prüfer codes; topology inference; distance matrix; tree realisation; leaf-to-leaf path length.

DOI: 10.1504/IJCNDS.2014.059439

International Journal of Communication Networks and Distributed Systems, 2014 Vol.12 No.2, pp.225 - 237

Received: 29 Oct 2012
Accepted: 02 Apr 2013

Published online: 21 Jun 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article