TR-169: Trade-Offs in Non-Reversing Diameter

Abstract

Consider a tree T with a number of extra edges (the bridges) added. We consider the notion of diameter, that is obtained by admitting only paths p with the property that for every bridge b in path p, no edge that is on the unique path (in T) between the endpoints of b is also in p or on the unique path between the two endpoints of any other bridge in p. (Such a path is called non-reversing.) We investigate the trade-off between the number of added bridges and the resulting diameter. Upper and lower bounds of the same order are obtained for all diameters of constant size, of size a( N) + 0 ( 1) or of size f(N) where f(N) grows faster than a(N). Some applications are given.