Constructing light spanners deterministically in near-linear time
From MaRDI portal
Publication:2077383
DOI10.1016/j.tcs.2022.01.021OpenAlexW2751315341MaRDI QIDQ2077383
Stephen Alstrup, Arnold Filtser, Christian Wulff-Nilsen, Morten Stöckel, Søren Dahlgaard
Publication date: 21 February 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1709.01960
Related Items
Online Spanners in Metric Spaces ⋮ Constructing Light Spanners Deterministically in Near-Linear Time
Cites Work
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- 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.
- 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
- Efficiency of a Good But Not Linear Set Union Algorithm
- 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
- The Greedy Spanner Is Existentially Optimal
- 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
- Light Spanners
- Automata, Languages and Programming
- Approximate Distance Oracles with Improved Query Time
