Graph spanners: A tutorial review

Peleg, 1989, Graph spanners, J. Graph Theory, 13, 99, 10.1002/jgt.3190130114 Awerbuch, 1985, Complexity of network synchronization, J. ACM, 32, 804, 10.1145/4221.4227 Bhatt, 1986, Optimal simulations of tree machines, 274 Gudmundsson, 2008, Geometric spanners, 360 Narasimhan, 2007 Abboud, 2018, A hierarchy of lower bounds for sublinear additive spanners, SIAM J. Comput., 47, 2203, 10.1137/16M1105815 Althöfer, 1993, On sparse spanners of weighted graphs, Discrete Comput. Geom., 9, 81, 10.1007/BF02189308 Kortsarz, 1994, Generating sparse 2-spanners, J. Algorithms, 17, 222, 10.1006/jagm.1994.1032 Peleg, 1989, An optimal synchronizer for the hypercube, SIAM J. Comput., 18, 740, 10.1137/0218050 Chew, 1989, There are planar graphs almost as good as the complete graph, J. Comput. System Sci., 39, 205, 10.1016/0022-0000(89)90044-5 Paul Erdős, Extremal problems in graph theory, in: Proceedings of the Symposium on Theory of Graphs and Its Applications, 1963, p. 2936. Erdős, 1970, Some extremal problems in graph theory, 377 Parter, 2014, Bypassing Erdős’ girth conjecture: Hybrid stretch and sourcewise spanners, 608 Baswana, 2003, A simple linear time algorithm for computing a (2k−1)-spanner of O(n1+1∕k) size in weighted graphs, 384 Woodruff, 2006, Lower bounds for additive spanners, emulators, and more, 389 Wenger, 1991, Extremal graphs with no C4’s, C6’s, or C10’s, J. Combin. Theory Ser. B, 52, 113, 10.1016/0095-8956(91)90097-4 Tits, 1959, Sur la trialité et certains groupes qui s’en déduisent, Publ. Math. Inst. Hautes Études Sci., 2, 14, 10.1007/BF02684706 Cai, 1994, NP-completeness of minimum spanner problems, Discrete Appl. Math., 48, 187, 10.1016/0166-218X(94)90073-6 Arora, 1996, Hardness of approximations, 399 Elkin, 2005, Approximating k–spanner problems for k>2, Theoret. Comput. Sci., 337, 249, 10.1016/j.tcs.2004.11.022 Elkin, 2007, The hardness of approximating spanner problems, Theory Comput. Syst., 41, 691, 10.1007/s00224-006-1266-2 Dinitz, 2016, Label cover instances with large girth and the hardness of approximating basic k-spanner, ACM Trans. Algorithms, 12, 25, 10.1145/2818375 Elkin, 2000, Strong inapproximability of the basic k-spanner problem, 636 Brandes, 1998, NP-completeness results for minimum planar spanners, Discrete Math. Theor. Comput. Sci., 3 Kobayashi, 2018, NP-hardness and fixed-parameter tractability of the minimum spanner problem, Theoret. Comput. Sci., 746, 88, 10.1016/j.tcs.2018.06.031 Kobayashi, 2019 Liestman, 1993, Additive graph spanners, Networks, 23, 343, 10.1002/net.3230230417 Filtser, 2016, The greedy spanner is existentially optimal, 9 Knudsen, 2014, Additive spanners: A simple construction, 277 Garay, 1998, A sublinear time distributed algorithm for minimum-weight spanning trees, SIAM J. Comput., 27, 302, 10.1137/S0097539794261118 Peleg, 2000, Distributed computing Borradaile, 2019, Greedy spanners are optimal in doubling metrics, 2371 Chandra, 1992, New sparseness results on graph spanners, 192 Elkin, 2014, Light spanners, 442 Elkin, 2016, Fast constructions of lightweight spanners for general graphs, ACM Trans. Algorithms, 12, 29, 10.1145/2836167 Chechik, 2018, Near-optimal light spanners, ACM Trans. Algorithms, 14, 33, 10.1145/3199607 Alstrup, 2019, Constructing light spanners deterministically in near-linear time, vol. 144, 4:1 Baswana, 2010, Additive spanners and (α, β)-spanners, ACM Trans. Algorithms, 7, 5, 10.1145/1868237.1868242 Pettie, 2009, Low distortion spanners, ACM Trans. Algorithms, 6, 7, 10.1145/1644015.1644022 Cygan, 2013, On pairwise spanners, 209 Kavitha, 2013, Small stretch pairwise spanners, 601 Kavitha, 2017, New pairwise spanners, Theory Comput. Syst., 61, 1011, 10.1007/s00224-016-9736-7 Michael Elkin, personal communication. Halperin, 1996 Thorup, 2006, Spanners and emulators with sublinear distance errors, 802 Cormen, 2009 Bodwin, 2016, Better distance preservers and additive spanners, 855 Elkin, 2004, (1+ε,β)–Spanner constructions for general graphs, SIAM J. Comput., 33, 608, 10.1137/S0097539701393384 Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie, New constructions of (α,β)–spanners and purely additive spanners, in: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2005, pp. 672–681. Baswana, 2007, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Random Struct. Algorithms, 30, 532, 10.1002/rsa.20130 Chechik, 2013, New additive spanners, 498 Miller, 2015, Improved parallel algorithms for spanners and hopsets, 192 Elkin, 2018, Efficient algorithms for constructing very sparse spanners and emulators, ACM Trans. Algorithms, 15, 1, 10.1145/3274651 Bollobás, 2005, Sparse distance preservers and additive spanners, SIAM J. Discrete Math., 19, 1029, 10.1137/S0895480103431046 Coppersmith, 2006, Sparse sourcewise and pairwise distance preservers, SIAM J. Discrete Math., 20, 463, 10.1137/050630696 Abboud, 2016, Error amplification for pairwise spanner lower bounds, 841 Bodwin, 2017, Linear size distance preservers, 600 Gajjar, 2017, Distance-preserving subgraphs of interval graphs Bodwin, 2019, On the structure of unique shortest paths in graphs, 2071 Abboud, 2017, The 4/3 additive spanner exponent is tight, J. ACM, 64, 28, 10.1145/3088511 Abboud, 2018, Reachability preservers: New extremal bounds and approximation algorithms, 1865 Elkin, 2017, Terminal embeddings, Theoret. Comput. Sci., 697, 1, 10.1016/j.tcs.2017.06.021 Aingworth, 1999, Fast estimation of diameter and shortest paths (without matrix multiplication), SIAM J. Comput., 28, 1167, 10.1137/S0097539796303421 Shang-En Huang, Seth Pettie, Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts, in: 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018. Bodwin, 2020 Woodruff, 2010, Additive spanners in nearly quadratic time, 463 Knudsen, 2017, Additive spanners and distance oracles in quadratic time Chlamtáč, 2017, Approximating spanners and directed Steiner forest: Upper and lower bounds, 534 Ben-Levy, 2020, New (α, β) spanners and hopsets, 1695 Elkin, 2019 Ahmed, 2020 Huang, 2019, Thorup–Zwick emulators are universally optimal hopsets, Inform. Process. Lett., 142, 9, 10.1016/j.ipl.2018.10.001 Michael Elkin, Ofer Neiman, Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC, in: The 31st ACM Symposium on Parallelism in Algorithms and Architectures, 2019, pp. 333–341. Elkin, 2020 Sigurd, 2004, Construction of minimum-weight spanners, 797 Michael Dinitz, Robert Krauthgamer, Directed spanners via flow-based linear programs, in: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC, 2011, pp. 323–332. Chlamtáč, 2012, Everywhere-sparse spanners via dense subgraphs Berman, 2013, Approximation algorithms for spanner problems and directed steiner forest, 93 Chlamtáč, 2016, Lowest-degree k-spanner: Approximation and hardness, Theory Comput., 12, 1, 10.4086/toc.2016.v012a015 Dinitz, 2016, Approximating low-stretch spanners, 821 Reyan Ahmed, Keaton Hamm, MohammadJavad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, Richard Spence, Approximation algorithms and an integer program for multi-level graph spanners, in: Proceedings of the Special Event on Analysis of Experimental Algorithms, 2019. Dinitz, 2019 Bertsimas, 1997 Ahmed, 2019 Elkin, 2005, Computing almost shortest paths, ACM Trans. Algorithms, 1, 283, 10.1145/1103963.1103968 Elkin, 2006, Efficient algorithms for constructing (1+ε, β)-spanners in the distributed and streaming models, Distrib. Comput., 18, 375, 10.1007/s00446-005-0147-2 Derbel, 2007, Deterministic distributed construction of linear stretch spanners in polylogarithmic time, 179 Derbel, 2008, On the locality of distributed sparse spanner construction, 273 Baswana, 2008, Streaming algorithm for graph spanners - Single pass and constant processing time per edge, Inform. Process. Lett., 106, 110, 10.1016/j.ipl.2007.11.001 Pettie, 2008, Distributed algorithms for ultrasparse spanners and linear size skeletons, 253 Elkin, 2011, Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners, ACM Trans. Algorithms, 7, 1, 10.1145/1921659.1921666 Lenzen, 2013, Efficient distributed source detection with limited bandwidth, 375 Kapralov, 2014, Spanners and sparsifiers in dynamic streams, 272 Censor-Hillel, 2016, Distributed construction of purely additive spanners, 129 Keren Censor-Hillel, Ami Paz, Noam Ravid, The sparsest additive spanner via multiple weigted BFS trees, in: 22nd International Conference on Principles of Distributed Systems, 2019. Michael Elkin, Shaked Matar, Near-additive spanners in low polynomial deterministic CONGEST time, in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019, pp. 531–540. Elkin, 2019 Peleg, 2000 Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang, On graph problems in a semi-streaming model, Departmental Papers (CIS), 2005, p. 236. Kook Jin Ahn, Sudipto Guha, Andrew McGregor, Graph sketches: sparsification, spanners, and subgraphs, in: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2012, pp. 5–14. Dor, 2000, All-pairs almost shortest paths, SIAM J. Comput., 29, 1740, 10.1137/S0097539797327908 Chang, 2018, Near-optimal distance emulator for planar graphs, 16:1 Thorup, 2001, Approximate distance oracles, 183 Roditty, 2005, Deterministic constructions of approximate distance oracles and spanners, 261 Baswana, 2006, Approximate distance oracles for unweighted graphs in expected O(n2) time, ACM Trans. Algorithms, 2, 557, 10.1145/1198513.1198518 Baswana, 2008, Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error, 609 Sommer, 2014, Shortest-path queries in static networks, ACM Comput. Surv., 46, 45, 10.1145/2530531 Backurs, 2018, Towards tight approximation bounds for graph diameter and eccentricities, 267 Choudhary, 2020, Extremal distances in directed graphs: Tight spanners and near-optimal approximation algorithms, 495 Abraham, 2018, Ramsey spanning trees and their applications, 1650 Chan, 2006, Spanners with slack, 196 Dragan, 2011, Spanners in sparse graphs, J. Comput. System Sci., 77, 1108, 10.1016/j.jcss.2010.10.002 Handke, 2000, Tree spanners for subgraphs and related tree covering problems, 206 Cai, 1995, Tree spanners, SIAM J. Discrete Math., 8, 359, 10.1137/S0895480192237403 Emek, 2008, Approximating minimum max-stretch spanning trees on unweighted graphs, SIAM J. Comput., 38, 1761, 10.1137/060666202 Álvarez-Miranda, 2018, Mixed-integer programming approaches for the tree t∗-spanner problem, Optim. Lett., 1 Singh, 2018, Artifical bee colony algorithm using problem-specific neighborhood strategies for the tree t-spanner problem, Appl. Soft Comput., 62, 110, 10.1016/j.asoc.2017.10.022 Sundar, 2019, A steady-state genetic algorithm for the tree t-spanner problem, 387 Kortsarz, 1994, Generating low-degree 2-spanners, SIAM J. Comput., 27, 1438, 10.1137/S0097539794268753 Sunil Arya, Gautam Das, David M Mount, Jeffrey S Salowe, Michiel Smid, Euclidean spanners: short, thin, and lanky, in: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC, 1995, pp. 489–498. Elkin, 2015, Optimal Euclidean spanners: Really short, thin, and lanky, J. ACM, 62, 1, 10.1145/2819008 Chan, 2015, New doubling spanners: Better and simpler, SIAM J. Comput., 44, 37, 10.1137/130930984 Gottlieb, 2015, A light metric spanner, 759 Chechik, 2010, Fault tolerant spanners for general graphs, SIAM J. Comput., 39, 3403, 10.1137/090758039 Ausiello, 2010, Computing graph spanners in small memory: fault-tolerance and streaming, Discrete Math. Algorithms Appl., 2, 591, 10.1142/S1793830910000905 Dinitz, 2011, Fault-tolerant spanners: Better and simpler, 169 Braunschvig, 2015, Fault tolerant additive and (μ,α)–spanners, Theoret. Comput. Sci., 580, 94, 10.1016/j.tcs.2015.02.036 Bilò, 2015, Improved purely additive fault-tolerant spanners, 167 Parter, 2017, Vertex fault tolerant additive spanners, Distrib. Comput., 30, 357, 10.1007/s00446-015-0252-9 Bodwin, 2019, A trivial yet optimal solution to vertex fault tolerant spanners, 541 Dinitz, 2020 Levcopoulos, 1998, Efficient algorithms for constructing fault-tolerant geometric spanners, 186 Bodwin, 2018, Optimal vertex fault tolerant spanners (for fixed stretch), 1884 Parter, 2013, Sparse fault-tolerant BFS trees, 779 Parter, 2015, Dual failure resilient BFS structure, 481 Manoj Gupta, Shahbaz Khan, Multiple source dual fault tolerant BFS Trees, in: 44th International Colloquium on Automata, Languages, and Programming, Vol. 80, ICALP, 2017, pp. 127:1–127:15. Bodwin, 2017, Preserving distances in very faulty graphs, 73:1 Ausiello, 2016, On resilient graph spanners, Algorithmica, 74, 1363, 10.1007/s00453-015-0006-x Ausiello, 2006, Small stretch spanners on dynamic graphs, J. Graph Algorithms Appl., 10, 365, 10.7155/jgaa.00133 Baswana, 2006, Dynamic algorithms for graph spanners, 76 Baswana, 2012, Fully dynamic algorithms for graph spanners, ACM Trans. Algorithms, 8, 35:1, 10.1145/2344422.2344425 Bodwin, 2016, Fully dynamic spanners with worst-case update time Aaron Bernstein, Sebastian Forster, Monika Henzinger, A deamortization approach for dynamic spanner and dynamic maximal matching, in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 1899–1918. Roditty, 2002, Roundtrip spanners and roundtrip routing in directed graphs, 844 Berman, 2011, Improved approximation for the directed spanner problem, 1 Zhu, 2017, Source-wise round-trip spanners, Inform. Process. Lett., 124, 42, 10.1016/j.ipl.2017.04.009 Zhu, 2018, Deterministic improved round-trip spanners, Inform. Process. Lett., 129, 57, 10.1016/j.ipl.2017.09.008 Cohen, 2000, Polylog-time and near-linear work approximation scheme for undirected shortest paths, J. ACM, 47, 132, 10.1145/331605.331610 Borradaile, 2017, Minor-free graphs have light spanners, 767 Busch, 2010, Concurrent counting is harder than queuing, Theoret. Comput. Sci., 411, 3823, 10.1016/j.tcs.2010.07.002 Shpungin, 2009, Near optimal multicriteria spanner constructions in wireless ad-hoc networks, 163 Baruch Awerbuch, Shay Kutten, David Peleg, Online load balancing in a distributed network, in: Proceedings of the 24th ACM Symposium on Theory of Computing, STOC, 1992, pp. 571–580. Cai, 1997, Computing visibility information in an inaccurate simple polygon, Internat. J. Comput. Geom. Appl., 7, 515, 10.1142/S0218195997000326 Thorup, 2001, Compact routing schemes, 1 Bandelt, 1986, Reconstructing the shape of a tree from observed dissimilarity data, Adv. Appl. Math., 7, 309, 10.1016/0196-8858(86)90038-2 Russel, 2005, Exploring protein folding trajectories using geometric spanners, 40 Choudhary, 2018