On the Maximum Number of Linearly Independent Cycles and Paths in a Network
The term network tomography, coined by Vardi, refers to the inference of certain internal characteristics of networks based on end-to-end measurements. The authors consider the problem of identifying additive link metrics in an arbitrary undirected network using measurement nodes and establishing paths/cycles between them. For a given placement of measurement nodes, they define and derive the "Link rank" of the network - the maximum number of linearly independent cycles/paths that may be established between the measurement nodes. They develop a polynomial time algorithm to compute a set of cycles/paths that achieves the maximum rank.