On the public citation graph

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators

https://doi.org/10.1145/3274651
0 signed · 99 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/jgt.3190130114openalex-snapshot
Graph spanners
inferredcites →https://doi.org/10.1007/3-540-45061-0_32openalex-snapshot
A Simple Linear Time Algorithm for Computing a (2k — 1)-Spanner of O(n 1+1/k ) Size in Weighted Graphs
inferredcites →https://doi.org/10.1007/3-540-46784-x_5openalex-snapshot
Proximity-Preserving Labeling Schemes and Their Applications
inferredcites →https://doi.org/10.1007/978-3-319-05446-9_10openalex-snapshot
An Entropy-Based Proof for the Moore Bound for Irregular Graphs
inferredcites →https://doi.org/10.1007/978-3-540-30140-0_10openalex-snapshot
Graph Decomposition Lemmas and Their Role in Metric Embedding Methods
inferredcites →https://doi.org/10.1007/978-3-540-30140-0_52openalex-snapshot
On Dynamic Shortest Paths Problems
inferredcites →https://doi.org/10.1007/978-3-540-73420-8_62openalex-snapshot
Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
inferredcites →https://doi.org/10.1007/bf01303516openalex-snapshot
Low diameter graph decompositions
inferredcites →https://doi.org/10.1007/bf02189308openalex-snapshot
On sparse spanners of weighted graphs
inferredcites →https://doi.org/10.1007/s00224-013-9444-5openalex-snapshot
Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs
inferredcites →https://doi.org/10.1007/s003730200002openalex-snapshot
The Moore Bound for Irregular Graphs
inferredcites →https://doi.org/10.1007/s00446-005-0147-2openalex-snapshot
Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models
inferredcites →https://doi.org/10.1007/s00446-009-0091-7openalex-snapshot
Distributed algorithms for ultrasparse spanners and linear size skeletons
inferredcites →https://doi.org/10.1016/j.aim.2011.08.003openalex-snapshot
Advances in metric embedding theory
inferredcites →https://doi.org/10.1016/j.ipl.2007.11.001openalex-snapshot
Streaming algorithm for graph spanners—single pass and constant processing time per edge
inferredcites →https://doi.org/10.1016/j.jcss.2005.04.002openalex-snapshot
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
inferredcites →https://doi.org/10.1016/j.jda.2009.03.001openalex-snapshot
A faster algorithm for the single source shortest path problem with few distinct positive lengths
inferredcites →https://doi.org/10.1016/j.tcs.2022.01.021openalex-snapshot
Constructing light spanners deterministically in near-linear time
inferredcites →https://doi.org/10.1109/focs.2006.45openalex-snapshot
Lower Bounds for Additive Spanners, Emulators, and More
inferredcites →https://doi.org/10.1109/focs.2011.85openalex-snapshot
A Nearly-m log n Time Solver for SDD Linear Systems
inferredcites →https://doi.org/10.1109/focs.2016.22openalex-snapshot
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
inferredcites →https://doi.org/10.1109/sfcs.1993.366822openalex-snapshot
Fast algorithms for constructing t-spanners and paths with stretch t
inferredcites →https://doi.org/10.1109/sfcs.1993.366823openalex-snapshot
Near-linear cost sequential and distributed constructions of sparse neighborhood covers
inferredcites →https://doi.org/10.1109/sfcs.1996.548477openalex-snapshot
Probabilistic approximation of metric spaces and its algorithmic applications
inferredcites →https://doi.org/10.1109/sfcs.1996.548504openalex-snapshot
All pairs almost shortest paths
inferredcites →https://doi.org/10.1137/0218050openalex-snapshot
An Optimal Synchronizer for the Hypercube
inferredcites →https://doi.org/10.1137/0405013openalex-snapshot
Routing with Polynomial Communication-Space Trade-Off
inferredcites →https://doi.org/10.1137/1.9780898719772openalex-snapshot
Distributed Computing: A Locality-Sensitive Approach
inferredcites →https://doi.org/10.1137/1.9781611973730.55openalex-snapshot
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
inferredcites →https://doi.org/10.1137/s0097539701393384openalex-snapshot
$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
inferredcites →https://doi.org/10.1137/s0097539794261295openalex-snapshot
Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
inferredcites →https://doi.org/10.1137/s0097539796303421openalex-snapshot
Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
inferredcites →https://doi.org/10.1137/s0895480103431046openalex-snapshot
Sparse Distance Preservers and Additive Spanners
inferredcites →https://doi.org/10.1145/1007352.1007407openalex-snapshot
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
inferredcites →https://doi.org/10.1145/1044731.1044732openalex-snapshot
Approximate distance oracles
inferredcites →https://doi.org/10.1145/1060590.1060665openalex-snapshot
Lower-stretch spanning trees
inferredcites →https://doi.org/10.1145/1103963.1103968openalex-snapshot
Computing almost shortest paths
inferredcites →https://doi.org/10.1145/1281100.1281128openalex-snapshot
A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
inferredcites →https://doi.org/10.1145/1400751.1400788openalex-snapshot
On the locality of distributed sparse spanner construction
inferredcites →https://doi.org/10.1145/1644015.1644022openalex-snapshot
Low distortion spanners
inferredcites →https://doi.org/10.1145/1868237.1868242openalex-snapshot
Additive spanners and (α, β)-spanners
inferredcites →https://doi.org/10.1145/2213977.2214015openalex-snapshot
Using petal-decompositions to build a low stretch spanning tree
inferredcites →https://doi.org/10.1145/2486159.2486180openalex-snapshot
Parallel graph decompositions using random shifts
inferredcites →https://doi.org/10.1145/2688073.2688103openalex-snapshot
Very Sparse Additive Spanners and Emulators
inferredcites →https://doi.org/10.1145/2755573.2755574openalex-snapshot
Improved Parallel Algorithms for Spanners and Hopsets
inferredcites →https://doi.org/10.1145/276698.276725openalex-snapshot
On approximating arbitrary metrices by tree metrics
inferredcites →https://doi.org/10.1145/2836167openalex-snapshot
Fast Constructions of Lightweight Spanners for General Graphs
inferredcites →https://doi.org/10.1145/2897518.2897555openalex-snapshot
The 4/3 additive spanner exponent is tight
inferredcites →https://doi.org/10.1145/2933057.2933094openalex-snapshot
Distributed Strong Diameter Network Decomposition
inferredcites →https://doi.org/10.1145/2933057.2933114openalex-snapshot
The Greedy Spanner is Existentially Optimal
inferredcites →https://doi.org/10.1145/331605.331610openalex-snapshot
Polylog-time and near-linear work approximation scheme for undirected shortest paths
inferredcites →https://doi.org/10.1145/4221.4227openalex-snapshot
Complexity of network synchronization
inferredcites →https://doi.org/10.1145/65950.65953openalex-snapshot
A trade-off between space and efficiency for routing tables
inferredcites →https://doi.org/10.5555/1070432.1070537openalex-snapshot
Graph distances in the streaming model: the value of space
inferredcites →https://doi.org/10.5555/1109557.1109645openalex-snapshot
Spanners and emulators with sublinear distance errors
inferredcites →https://doi.org/10.5555/1255378.1255381openalex-snapshot
A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
inferredcites →https://doi.org/10.5555/127787.127848openalex-snapshot
Decomposing graphs into regions of small diameter
inferredcites →https://doi.org/10.5555/2627817.2627853openalex-snapshot
New additive spanners
inferredcites →https://doi.org/10.5555/2722129.2722184openalex-snapshot
A linear-size logarithmic stretch path-reporting distance oracle for general graphs
inferredcites →https://doi.org/10.5555/2805875.2805976openalex-snapshot
On sparse spanners of weighted graphs
inferredcites →https://doi.org/10.5555/3039686.3039722openalex-snapshot
A hierarchy of lower bounds for sublinear additive spanners

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-031-75409-8_17openalex-snapshot
Lightweight Near-Additive Spanners
inferred← citeshttps://doi.org/10.1007/978-3-032-26465-7_19openalex-snapshot
Fast Distributed Computation of Compact Routing Schemes
inferred← citeshttps://doi.org/10.1007/s00446-023-00442-4openalex-snapshot
Time-optimal construction of overlay networks
inferred← citeshttps://doi.org/10.1007/s00446-025-00482-yopenalex-snapshot
Massively parallel algorithms for approximate shortest paths
inferred← citeshttps://doi.org/10.1007/s00446-025-00503-wopenalex-snapshot
Constant-round spanners and shortest paths in congested clique and MPC
inferred← citeshttps://doi.org/10.1007/s00453-022-01053-4openalex-snapshot
Faster Cut Sparsification of Weighted Graphs
inferred← citeshttps://doi.org/10.1016/j.cosrev.2020.100253openalex-snapshot
Graph spanners: A tutorial review
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.05.035openalex-snapshot
The sparsest additive spanner via multiple weighted BFS trees
inferred← citeshttps://doi.org/10.1016/j.tcs.2022.01.021openalex-snapshot
Constructing light spanners deterministically in near-linear time
inferred← citeshttps://doi.org/10.1080/17445760.2026.2616783openalex-snapshot
Practical parallel algorithms for compact spanners on real world graphs
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00099openalex-snapshot
Fast Deterministic Fully Dynamic Distance Approximation
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00141openalex-snapshot
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)
inferred← citeshttps://doi.org/10.1109/lra.2023.3320011openalex-snapshot
D-Lite: Navigation-Oriented Compression of 3D Scene Graphs for Multi-Robot Collaboration
inferred← citeshttps://doi.org/10.1111/cgf.14789openalex-snapshot
Faster Edge‐Path Bundling through Graph Spanners
inferred← citeshttps://doi.org/10.1137/1.9781611975994.64openalex-snapshot
Lossless Prioritized Embeddings
inferred← citeshttps://doi.org/10.1137/1.9781611976465.110openalex-snapshot
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
inferred← citeshttps://doi.org/10.1137/1.9781611977073.132openalex-snapshot
Near-Optimal Spanners for General Graphs in (Nearly) Linear Time
inferred← citeshttps://doi.org/10.1137/20m1312630openalex-snapshot
Distributed Spanner Approximation
inferred← citeshttps://doi.org/10.1137/21m1436221openalex-snapshot
Lossless Prioritized Embeddings
inferred← citeshttps://doi.org/10.1137/23m1589670openalex-snapshot
A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions
inferred← citeshttps://doi.org/10.1145/3295500.3356182openalex-snapshot
Slim graph
inferred← citeshttps://doi.org/10.1145/3357713.3384268openalex-snapshot
Faster parallel algorithm for approximate shortest path
inferred← citeshttps://doi.org/10.1145/3382734.3405701openalex-snapshot
Distributed Construction of Light Networks
inferred← citeshttps://doi.org/10.1145/3406325.3451043openalex-snapshot
Clan embeddings into trees, and low treewidth graphs
inferred← citeshttps://doi.org/10.1145/3465084.3467928openalex-snapshot
Constant-Round Spanners and Shortest Paths in Congested Clique and MPC
inferred← citeshttps://doi.org/10.1145/3465084.3467932openalex-snapshot
Time-Optimal Construction of Overlay Networks
inferred← citeshttps://doi.org/10.1145/3527213openalex-snapshot
Exponentially Faster Shortest Paths in the Congested Clique
inferred← citeshttps://doi.org/10.1145/3564246.3585185openalex-snapshot
A Unified Framework for Light Spanners
inferred← citeshttps://doi.org/10.1145/3577193.3593727openalex-snapshot
Scalable algorithms for compact spanners on real world graphs
inferred← citeshttps://doi.org/10.1145/3626183.3659978openalex-snapshot
Massively Parallel Algorithms for Approximate Shortest Paths
inferred← citeshttps://doi.org/10.1145/3815589openalex-snapshot
BLR-Krylov: A Single-GPU Iterative SpMM Framework with Communication Avoidance and Block Low-Rank Optimization
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2019.6openalex-snapshot
On Strong Diameter Padded Decompositions
inferred← citeshttps://doi.org/10.4230/lipics.disc.2019.7openalex-snapshot
Message Reduction in the LOCAL Model Is a Free Lunch
inferred← citeshttps://doi.org/10.4230/lipics.opodis.2021.16openalex-snapshot
An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2020.11openalex-snapshot
An FPT Algorithm for Minimum Additive Spanner Problem
inferred← citeshttps://doi.org/10.4230/lipics.swat.2022.23openalex-snapshot
Almost Shortest Paths with Near-Additive Error in Weighted Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.1912.08950openalex-snapshot
Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics
inferred← citeshttps://doi.org/10.48550/arxiv.2106.15596openalex-snapshot
Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.