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.

Kamala Krithivasan

Algorithms

Encoding (symbols)

Topology

Distance matrices

Graphs

Network tomography

PATHS

Topology inference

TREE-REALISATION

Trees

Trees (mathematics)

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

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

International Journal of Communication Networks and Distributed Systems

This paper proposes a heuristic approach for the distance realization problem, which arises in Network Tomography. Network Tomography is the study of estimating internal network structure and link-level performance from end-to-end measurements. A distance realization problem is to reconstruct a graph or topology from its distance matrix, i.e., the matrix containing the pairwise distances between the terminal nodes. The graph, thus realized from the pairwise distances of terminal nodes, can either be a tree or a general graph. There are efficient polynomial algorithms developed for the case of tree realization. However, the problem of finding optimal realization (i.e., the total length of the graph realized is minimum) of distance matrix for a general graph is shown to be NP-hard. Our proposed heuristic approach for distance realization consists of three stages: (i) find a closer tree realizable distance matrix based on the shortest paths, (ii) construct a tree and (iii) fix the differences between the tree realizable distance matrix and the original distance matrix. It also attempts to maximize the 'entropy of betweenness-centrality' measure in the network while satisfying the distance constraints. © 2013 IEEE.

2013 IEEE International Conference on Advanced Networks and Telecommunications Systems, ANTS 2013

Distance realization problem in Network Tomography: A heuristic approach

OLYMPIADS IN INFORMATICS

On a Metodology for Creating School Curricula in Computing

2008 The 3rd International Conference on Grid and Pervasive Computing - Workshops

Improving the Efficiency of Network Topology Discovery

Proceedings of the 8th ACM SIGCOMM conference on Internet measurement conference - IMC '08

Traceroute probe method and forward IP path inference

Information Processing Letters

On the longest path algorithm for reconstructing trees from distance matrices

Spanning Trees and Optimization Problems

Journal	International Journal of Communication Networks and Distributed Systems
Publisher	Inderscience Publishers
ISSN	17543916
Open Access	No