Incubators vs Zombies: Fault-Tolerant, Short, Thin and Lanky Spanners for Doubling Metrics

Recently Elkin and Solomon gave a construction of spanners for doubling metrics that has constant maximum degree, hop-diameter O(log n) and lightness O(log n) (i.e., weight O(log n)·w(MST)). This resolves a long standing conjecture proposed by Arya et al. in a seminal STOC 1995 paper. However, Elkin and Solomon’s spanner construction is extremely complicated; we offer a simple alternative construction that is very intuitive and is based on the standard technique of net tree with cross edges. Indeed, our approach can be readily applied to our previous construction of k-fault tolerant spanners (ICALP 2012) to achieve k-fault tolerance, maximum degree O(k2), hop-diameter O(log n) and lightness O(k3 log n). ∗Department of Computer Science, The University of Hong Kong †{hubert, mfli, lning} @ cs.hku.hk ar X i