17. Light-Weight Spanners
Society for Industrial and Applied Mathematics eBooks · 2000
In Section 15.2 we discussed the representation of graphs by spanning trees and mentioned two types of trees, namely, the MST and the SPT. These trees optimize the total weight and the root-stretch of the tree, respectively. The problem addressed here is how to handle situations in which it is desirable to have a spanning tree enjoying both low weight and stretch simultaneously. The same need may arise with any of our other types of locality-preserving skeletal representations. In this chapter we discuss possible modifications to our earlier constructions that lead to light-weight spanning subgraphs. 17.1 Light, low-stretch trees 17.1.1 MST, SPT and SLT Suppose that we are given a weighted graph G and need to construct a spanning tree T achieving near optimal performance in both the root stretch and the weight measures. Ideally, it would be best if it were possible to use either an SPT or an MST for this purpose. Unfortunately, it turns out that the weight and stretch requirements are sometimes contradictory. In particular, in an n-vertex graph, the weight of an SPT might be up to n times as large as that of an MST, i.e., . Analogously, the depth of an MST with respect to a given root r might be up to n times as high as that of an SPT, i.e., . Example: Depth/weight anomalies. In the weighted graph G shown in Figure 17.1, the weight of the shortest path tree with respect to the root 1 is , whereas , yielding a ratio approaching n − 1 as W tends to infinity. In contrast, in the weighted graph G shown in Figure 17.2, the depth of the minimum weight tree is Depth , whereas Depth , yielding a ratio approaching n − 1 as W tends to zero. A possible approach to overcoming this problem is to attempt to construct a tree simultaneously approximating both an SPT and an MST, i.e., optimizing Stretch(T) and ω(T) simultaneously. Definition 17.1.1 [Shallow-light tree]: A shallow-light tree (or SLT) for a weighted graph and a root vertex is a spanning tree T with constant weight ratio and root-stretch, i.e., such that and ω(T)/ω(MST) are both bounded by a constant.