Constructing Light Spanners Deterministically in Near-Linear Time
From MaRDI portal
Publication:5075736
DOI10.4230/LIPIcs.ESA.2019.4OpenAlexW2978584836MaRDI QIDQ5075736
Arnold Filtser, Christian Wulff-Nilsen, Morten Stöckel, Stephen Alstrup, Søren Dahlgaard
Publication date: 11 May 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11125/pdf/LIPIcs-ESA-2019-4.pdf/
Related Items (4)
Light Euclidean Spanners with Steiner Points ⋮ A fast algorithm for source-wise round-trip spanners ⋮ The Greedy Spanner Is Existentially Optimal ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion
Cites Work
- Unnamed Item
- Unnamed Item
- On dynamic shortest paths problems
- An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM
- On sparse spanners of weighted graphs
- Spanners and message distribution in networks.
- Constructing light spanners deterministically in near-linear time
- On notions of distortion and an almost minimum spanning tree with constant average distortion
- Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
- Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
- Approximate Distance Oracles with Improved Bounds
- Approximate distance oracles
- Complexity of network synchronization
- Graph spanners
- An On-Line Edge-Deletion Problem
- A Fast Algorithm for Constructing Sparse Euclidean Spanners
- Near-Optimal Light Spanners
- Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- Fast Constructions of Lightweight Spanners for General Graphs
- Fully-dynamic minimum spanning forest with improved worst-case update time
- Compact routing schemes with improved stretch
- Approximate distance oracles with constant query time
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- New deterministic approximation algorithms for fully dynamic matching
- The Greedy Spanner is Existentially Optimal
- Light Spanners
- Automata, Languages and Programming
- Approximate Distance Oracles with Improved Query Time
This page was built for publication: Constructing Light Spanners Deterministically in Near-Linear Time
