[1]   Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares: On sparse spanners of weighted graphs. Discrete Comput. Geom., 9(1):81–100, 1993. [doi:10.1007/BF02189308]

[2]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. Preliminary version in FOCS’92. [doi:10.1145/278298.278306]

[3]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]

[4]   Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie: Additive spanners and (α,β)-spanners. ACM Trans. Algorithms, 7(1):5:1–5:26, 2010. Preliminary version in SODA’05. [doi:10.1145/1868237.1868242]

[5]   Mohsen Bayati, Andrea Montanari, and Amin Saberi: Generating random graphs with large girth. In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09), pp. 566–575. ACM Press, 2009. ACM DL. [arXiv:0811.2853]

[6]   Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev: Improved approximation for the directed spanner problem. In Proc. 38th Internat. Colloq. on Automata, Languages and Programming (ICALP’11), volume 6755 of LNCS, pp. 1–12. Springer, 2011. [doi:10.1007/978-3-642-22006-7_1, arXiv:1012.4062]

[7]   Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff: Transitive-closure spanners. SIAM J. Comput., 41(6):1380–1425, 2012. Preliminary version in SODA’09. [doi:10.1137/110826655, arXiv:0808.1787]

[8]   T.-H. Hubert Chan, Michael Dinitz, and Anupam Gupta: Spanners with slack. In Proc. 14th Ann. European Symp. on Algorithms (ESA’06), pp. 196–207. Springer, 2006. [doi:10.1007/11841036_20]

[9]   Barun Chandra, Gautam Das, Giri Narasimhan, and José Soares: New sparseness results on graph spanners. Internat. J. Comput. Geom. Appl., 5(1):125–144, 1995. Preliminary version in SoCG’92. [doi:10.1142/S0218195995000088]

[10]   Shiri Chechik: New additive spanners. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 498–512. ACM Press, 2013. [doi:10.1137/1.9781611973105.36]

[11]   Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty: Fault tolerant spanners for general graphs. SIAM J. Comput., 39(7):3403–3423, 2010. Preliminary version in STOC’09. [doi:10.1137/090758039]

[12]   Eden Chlamtáč and Michael Dinitz: Lowest degree k-spanner: Approximation and hardness. In Proc. 17th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’14), volume 28 of LIPIcs, pp. 80–95. Springer, 2014. [doi:10.4230/LIPIcs.APPROX-RANDOM.2014.80]

[13]   Eden Chlamtáč, Michael Dinitz, and Robert Krauthgamer: Everywhere-sparse spanners via dense subgraphs. In Proc. 53rd FOCS, pp. 758–767. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.61, arXiv:1205.0144]

[14]   Michael Dinitz, Guy Kortsarz, and Ran Raz: Label cover instances with large girth and the hardness of approximating basic k-spanner. ACM Trans. Algorithms, 12(2):25:1–25:16, 2016. Preliminary version in ICALP’12. [doi:10.1145/2818375, arXiv:1203.0224]

[15]   Michael Dinitz and Robert Krauthgamer: Directed spanners via flow-based linear programs. In Proc. 43rd STOC, pp. 323–332. ACM Press, 2011. [doi:10.1145/1993636.1993680, arXiv:1011.3701]

[16]   Michael Dinitz and Robert Krauthgamer: Fault-tolerant spanners: Better and simpler. In Proc. 30th Symp. on Principles of Distributed Comput. (PODC’11), pp. 169–178. ACM Press, 2011. [doi:10.1145/1993806.1993830, arXiv:1101.5753]

[17]   Yevgeniy Dodis and Sanjeev Khanna: Designing networks with bounded pairwise distance. In Proc. 31st STOC, pp. 750–759. ACM Press, 1999. [doi:10.1145/301250.301447]

[18]   Michael Elkin and David Peleg: Strong inapproximability of the basic k-spanner problem. In Proc. 27th Internat. Colloq. on Automata, Languages and Programming (ICALP’00), pp. 636–647. Springer, 2000. [doi:10.1007/3-540-45022-X_54]

[19]   Michael Elkin and David Peleg: Approximating k-spanner problems for k > 2. Theoret. Comput. Sci., 337(1-3):249–277, 2005. Preliminary version in IPCO’01. [doi:10.1016/j.tcs.2004.11.022]

[20]   Michael Elkin and David Peleg: The hardness of approximating spanner problems. Theory Comput. Sys., 41(4):691–729, 2007. Preliminary version in STACS’00. [doi:10.1007/s00224-006-1266-2]

[21]   Michael Elkin and Shay Solomon: Fast constructions of lightweight spanners for general graphs. ACM Trans. Algorithms, 12(3):29:1–29:21, 2016. Preliminary version in SODA’13. [doi:10.1145/2836167, arXiv:1207.1668]

[22]   Guy Kortsarz: On the hardness of approximating spanners. Algorithmica, 30(3):432–450, 2001. Preliminary version in APPROX’98. [doi:10.1007/s00453-001-0021-y]

[23]   Guy Kortsarz and David Peleg: Generating sparse 2-spanners. J. Algorithms, 17(2):222–236, 1994. Preliminary version in SWAT’92. [doi:10.1006/jagm.1994.1032]

[24]   Guy Kortsarz and David Peleg: Generating low-degree 2-spanners. SIAM J. Comput., 27(5):1438–1456, 1998. Preliminary version in SODA’94. [doi:10.1137/S0097539794268753]

[25]   David Peleg and Alejandro A. Schäffer: Graph spanners. J. Graph Theory, 13(1):99–116, 1989. [doi:10.1002/jgt.3190130114]

[26]   David Peleg and Jeffrey D. Ullman: An optimal synchronizer for the hypercube. SIAM J. Comput., 18(4):740–747, 1989. Preliminary version in PODC’87. [doi:10.1137/0218050]

[27]   Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Preliminary version in STOC’95. [doi:10.1137/S0097539795280895]

[28]   Mohit Singh and Lap Chi Lau: Approximating minimum bounded degree spanning trees to within one of optimal. J. ACM, 62(1):1:1–1:19, 2015. Preliminary version in STOC’07. [doi:10.1145/2629366]

[29]   Mikkel Thorup and Uri Zwick: Compact routing schemes. In Proc. 13th Ann. ACM Symp. on Parallel Algorithms and Architectures (SPAA’01), pp. 1–10. ACM Press, 2001. [doi:10.1145/378580.378581]

[30]   Mikkel Thorup and Uri Zwick: Approximate distance oracles. J. ACM, 52(1):1–24, 2005. Preliminary version in STOC’01. [doi:10.1145/1044731.1044732]