28 papers:
STOC-2014-Solomon #fault tolerance #metric- From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics (SS), pp. 363–372.
ICALP-v1-2014-ElkinNS- Light Spanners (ME, ON, SS), pp. 442–452.
- ICALP-v2-2014-Parter #hybrid
- Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners (MP), pp. 608–619.
PODS-2013-FaginKRV #framework #information management #named- Spanners: a formal framework for information extraction (RF, BK, FR, SV), pp. 37–48.
- STOC-2013-ElkinS
- Optimal euclidean spanners: really short, thin and lanky (ME, SS), pp. 645–654.
- ICALP-v1-2013-ChanLNS
- New Doubling Spanners: Better and Simpler (THHC, ML, LN, SS), pp. 315–327.
- ICALP-v1-2013-KavithaV
- Small Stretch Pairwise Spanners (TK, NMV), pp. 601–612.
- PODS-2012-AhnGM #graph #sketching
- Graph sketches: sparsification, spanners, and subgraphs (KJA, SG, AM), pp. 5–14.
- ICALP-v1-2012-ChanLN #bound #fault tolerance #metric
- Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree (THHC, ML, LN), pp. 182–193.
- ICALP-v1-2012-DinitzKR #approximate #scalability
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner (MD, GK, RR), pp. 290–301.
OSDI-2012-CorbettDEFFFGGHHHKKLLMMNQRRSSTWW #database #named- Spanner: Google’s Globally-Distributed Database (JCC, JD, ME, AF, CF, JJF, SG, AG, CH, PH, WCH, SK, EK, HL, AL, SM, DM, DN, SQ, RR, LR, YS, MS, CT, RW, DW), pp. 261–264.
- STOC-2011-DinitzK #linear #source code
- Directed spanners via flow-based linear programs (MD, RK), pp. 323–332.
- ICALP-v1-2011-BermanBGRWY #transitive
- Steiner Transitive-Closure Spanners of Low-Dimensional Posets (PB, AB, EG, SR, DPW, GY), pp. 760–772.
- ICALP-v1-2011-BermanBMRY #approximate #problem
- Improved Approximation for the Directed Spanner Problem (PB, AB, KM, SR, GY), pp. 1–12.
- ICALP-v1-2010-BonichonGHP
- Plane Spanners of Maximum Degree Six (NB, CG, NH, LP), pp. 19–30.
- ICALP-v1-2010-Woodruff #polynomial
- Additive Spanners in Nearly Quadratic Time (DPW), pp. 463–474.
- STOC-2009-ChechikLPR #fault tolerance #graph
- Fault-tolerant spanners for general graphs (SC, ML, DP, LR), pp. 435–444.
- ICALP-A-2008-DraganFG #graph
- Spanners in Sparse Graphs (FFD, FVF, PAG), pp. 597–608.
- ICALP-2007-Elkin #algorithm #maintenance #streaming
- Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners (ME), pp. 716–727.
- ICALP-2007-Pettie
- Low Distortion Spanners (SP), pp. 78–89.
- STOC-2006-Klein #graph #set
- A subset spanner for Planar graphs, : with application to subset TSP (PNK), pp. 749–756.
- ICALP-2005-RodittyTZ #approximate #distance
- Deterministic Constructions of Approximate Distance Oracles and Spanners (LR, MT, UZ), pp. 261–272.
- ICALP-2003-BaswanaS #algorithm #graph #linear
- A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n1+1/k) Size in Weighted Graphs (SB, SS), pp. 384–296.
- STOC-2001-ElkinP #graph
- (1+ε,β)-Spanner Constructions for General Graphs (ME, DP), pp. 173–182.
- ICALP-2000-ElkinP #problem
- Strong Inapproximability of the Basic k-Spanner Problem (ME, DP), pp. 636–647.
- STOC-1998-LevcopoulosNS #algorithm #fault tolerance #geometry #performance
- Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners (CL, GN, MHMS), pp. 186–195.
- STOC-1998-RaoS #approximate #geometry #graph
- Approximating Geometrical Graphs via “Spanners” and “Banyans” (SR, WDS), pp. 540–550.
- STOC-1995-AryaDMSS
- Euclidean spanners: short, thin, and lanky (SA, GD, DMM, JSS, MHMS), pp. 489–498.
