On the public citation graph
Fast Constructions of Lightweight Spanners for General Graphs
0 signed · 59 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/jcss.1997.1545openalex-snapshot
The Space Complexity of Approximating the Frequency Moments
inferredcites →https://doi.org/10.1007/11523468_22openalex-snapshot
Deterministic Constructions of Approximate Distance Oracles and 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-46541-3_16openalex-snapshot
An Approximate L p-Difference Algorithm for Massive Data Streams
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-540-30140-0_52openalex-snapshot
On Dynamic Shortest Paths Problems
inferredcites →https://doi.org/10.1007/bf02189308openalex-snapshot
On sparse spanners of weighted 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.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.jalgor.2003.09.001openalex-snapshot
Deterministic sorting in O(nloglogn) time and linear space
inferredcites →https://doi.org/10.1016/s0022-0000(05)80064-9openalex-snapshot
Trans-dichotomous algorithms for minimum spanning trees and shortest paths
inferredcites →https://doi.org/10.1109/focs.2004.48openalex-snapshot
On the Streaming Model Augmented with a Sorting Primitive
inferredcites →https://doi.org/10.1109/focs.2006.45openalex-snapshot
Lower Bounds for Additive Spanners, Emulators, and More
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.2002.1181890openalex-snapshot
Integer sorting in O(n√(log log n)) expected time and linear space
inferredcites →https://doi.org/10.1137/0215072openalex-snapshot
On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
inferredcites →https://doi.org/10.1137/0218050openalex-snapshot
An Optimal Synchronizer for the Hypercube
inferredcites →https://doi.org/10.1137/s0097539700382947openalex-snapshot
Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
inferredcites →https://doi.org/10.1137/s0097539701393384openalex-snapshot
$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
inferredcites →https://doi.org/10.1137/s0097539796309764openalex-snapshot
Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k -MST, and Related Problems
inferredcites →https://doi.org/10.1137/s0097539799361701openalex-snapshot
An Approximate L 1 -Difference Algorithm for Massive Data Streams
inferredcites →https://doi.org/10.1142/s0218195991000049openalex-snapshot
THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
inferredcites →https://doi.org/10.1142/s0218195997000193openalex-snapshot
A Fast Algorithm for Constructing Sparse Euclidean Spanners
inferredcites →https://doi.org/10.1145/1103963.1103968openalex-snapshot
Computing almost shortest paths
inferredcites →https://doi.org/10.1145/142675.142717openalex-snapshot
New sparseness results on graph spanners
inferredcites →https://doi.org/10.1145/1868237.1868242openalex-snapshot
Additive spanners and (α, β)-spanners
inferredcites →https://doi.org/10.1145/1921659.1921666openalex-snapshot
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
inferredcites →https://doi.org/10.1145/201019.201022openalex-snapshot
A randomized linear-time algorithm to find minimum spanning trees
inferredcites →https://doi.org/10.1145/2213977.2214038openalex-snapshot
The traveling salesman problem
inferredcites →https://doi.org/10.1145/276698.276868openalex-snapshot
Approximating geometrical graphs via “spanners” and “banyans”
inferredcites →https://doi.org/10.1145/290179.290180openalex-snapshot
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
inferredcites →https://doi.org/10.1145/301250.301383openalex-snapshot
Worst-case and amortised optimality in union-find (extended abstract)
inferredcites →https://doi.org/10.1145/323596.323621openalex-snapshot
Communication-time trade-offs in network synchronization
inferredcites →https://doi.org/10.1145/355541.355562openalex-snapshot
A minimum spanning tree algorithm with inverse-Ackermann type complexity
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/2805875.2805976openalex-snapshot
On sparse spanners of weighted graphs
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1016/j.cosrev.2020.100253openalex-snapshot
Graph spanners: A tutorial review
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.1111/cgf.14789openalex-snapshot
Faster Edge‐Path Bundling through Graph Spanners
inferred← citeshttps://doi.org/10.1137/1.9781611974782.41openalex-snapshot
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
inferred← citeshttps://doi.org/10.1137/1.9781611976465.113openalex-snapshot
Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
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/18m1210678openalex-snapshot
The Greedy Spanner Is Existentially Optimal
inferred← citeshttps://doi.org/10.1145/2888451.2888479openalex-snapshot
Detecting Community Structures in Social Networks by Graph Sparsification
inferred← citeshttps://doi.org/10.1145/3274651openalex-snapshot
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
inferred← citeshttps://doi.org/10.1145/3382734.3405701openalex-snapshot
Distributed Construction of Light Networks
inferred← citeshttps://doi.org/10.1145/3564246.3585185openalex-snapshot
A Unified Framework for Light Spanners
inferred← citeshttps://doi.org/10.1186/s12859-021-04539-0openalex-snapshot
HESML: a real-time semantic measures library for the biomedical domain with a reproducible survey
inferred← citeshttps://doi.org/10.46298/theoretics.25.2openalex-snapshot
An Alternate Proof of Near-Optimal Light Spanners
inferred← citeshttps://doi.org/10.48550/arxiv.2106.15596openalex-snapshot
Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
inferred← citeshttps://doi.org/10.48550/arxiv.2111.13748openalex-snapshot
A Unified Framework of Light Spanners II: Fine-Grained Optimality
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.