Abstract
Graph spanners are sparse subgraphs that preserve the distances of the original graph, up to some small multiplicative factor or additive term (known as the stretch of the spanner). A number of algorithms are known for constructing sparse spanners with small multiplicative or additive stretch. Recently, the problem of constructing fault-tolerant multiplicative spanners for general graphs was given some algorithms. This paper addresses the analogous problem of constructing fault tolerant additive spanners for general graphs.
We establish the following general result. Given an n-vertex graph G, if H 1 is an ordinary additive spanner for G with additive stretch α, and H 2 is a fault tolerant multiplicative spanner for G, resilient against up to f edge failures, with multiplicative stretch μ, then H = H 1 ∪ H 2 is an additive fault tolerant spanner of G, resilient against up to f edge failures, with additive stretch \(O(\tilde{f}(\alpha+\mu))\) where \(\tilde{f}\) is the number of failures that have actually occurred \((\tilde{f}\leq f)\).
This allows us to derive a poly-time algorithm \({\texttt Span}^{f-t}_{add}\) for constructing an additive fault tolerant spanner H of G, relying on the existence of algorithms for constructing fault tolerant multiplicative spanners and (ordinary) additive spanners. In particular, based on some known spanner construction algorithms, we show how to construct for any n-vertex graph G an additive fault tolerant spanner with additive stretch \(O(\tilde{f})\) and size O(fn 4/3).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167–1181 (1999)
Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry 9, 81–100 (1993)
Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proc. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 591–602 (2006)
Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and (α, β)-spanners. ACM Trans. on Algo. 7, A.5 (2010)
Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: Proc. 41st ACM Symp. on Theory of Computing (STOC), pp. 435–444 (2009)
Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discrete & Computational Geometry 32, 2004 (2003)
Dinitz, M., Krauthgamer, R.: Fault-Tolerant Spanners: Better and Simpler. In: 30th ACM Symp. on Principles of Distributed Computing (PODC), pp. 169–178 (2011)
Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Computing 29(5), 1740–1759 (2000)
Elkin, M., Peleg, D.: (1 + ε, β)-spanner constructions for general graphs. SIAM J. Computing 33(3), 608–631 (2004)
Farley, A.M., Proskurowski, A., Zappala, D., Windisch, K.: Spanners and message distribution in networks. Discrete Applied Mathematics 137(2), 159–171 (2004)
Levcopoulos, C., Narasimhan, G., Smid, M.: Efficient algorithms for constructing fault-tolerant geometric spanners. In: Proc. 30th ACM Symp. on Theory of Computing (STOC), pp. 186–195 (1998)
Lukovszki, T.: New Results on Fault Tolerant Geometric Spanners. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol. 1663, pp. 193–204. Springer, Heidelberg (1999)
Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Computing 18(2), 740–747 (1989)
Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510–530 (1989)
Pettie, S.: Low distortion spanners. ACM Transactions on Algorithms 6(1) (2009)
Roditty, L., Thorup, M., Zwick, U.: Deterministic Constructions of Approximate Distance Oracles and Spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 261–272. Springer, Heidelberg (2005)
Thorup, M., Zwick, U.: Compact routing schemes. In: Proc. 13th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 1–10 (2001)
Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1–24 (2005)
Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: 17th Symp. on Discrete Algorithms (SODA), pp. 802–809. ACM-SIAM (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Braunschvig, G., Chechik, S., Peleg, D. (2012). Fault Tolerant Additive Spanners. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds) Graph-Theoretic Concepts in Computer Science. WG 2012. Lecture Notes in Computer Science, vol 7551. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34611-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-34611-8_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34610-1
Online ISBN: 978-3-642-34611-8
eBook Packages: Computer ScienceComputer Science (R0)