A fast algorithm for source-wise round-trip spanners
type: Item
instance of: scholarly article
title: A fast algorithm for source-wise round-trip spanners
author: Chun Jiang Zhu
author: Song Han
author: Kam-Yiu Lam
published in: Theoretical Computer Science
publication date: 2021-06-23T00:00:00Z
full work available at URL: https://arxiv.org/abs/2004.05721
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7362189
zbMATH Keywords: graph spanners
zbMATH Keywords: round-trip spanners
zbMATH Keywords: graph algorithms
zbMATH Keywords: graph partitioning
MaRDI profile type: Publication
OpenAlex ID: W3164304453
cites work: The 4/3 additive spanner exponent is tight
cites work: Graph spanners: a tutorial review
cites work: Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
cites work: Constructing Light Spanners Deterministically in Near-Linear Time
cites work: On sparse spanners of weighted graphs
cites work: Additive spanners and (α, β)-spanners
cites work: Linear Size Distance Preservers
cites work: New Additive Spanners
cites work: Constant girth approximation for directed graphs in subquadratic time
cites work: Size-estimation framework with applications to transitive closure and reachability
cites work: Sparse Sourcewise and Pairwise Distance Preservers
cites work: Q4252392
cites work: Compact roundtrip routing in directed networks (extended abstract)
cites work: On Pairwise Spanners
cites work: $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
cites work: Routing under balance
cites work: Q5543308
cites work: New Pairwise Spanners
cites work: Small Stretch Pairwise Spanners
cites work: An O(nm) time algorithm for finding the min length directed cycle in a graph
cites work: Q4607979
cites work: Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
cites work: Graph spanners
cites work: Low distortion spanners
cites work: Automata, Languages and Programming
cites work: Roundtrip spanners and roundtrip routing in directed graphs
cites work: Approximate distance oracles
cites work: Spanners and emulators with sublinear distance errors
cites work: Additive Spanners in Nearly Quadratic Time
cites work: Source-wise round-trip spanners
cites work: Deterministic improved round-trip spanners
DOI: 10.1016/J.TCS.2021.05.019
Recommended article: Deterministic improved round-trip spanners
Recommended article: Q4829021
Recommended article: Roundtrip spanners and roundtrip routing in directed graphs
Recommended article: Q4607979
Recommended article: Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
Recommended article: Approximation algorithms for somek-source shortest paths spanning tree problems
Recommended article: Approximation algorithms for quickest spanning tree problems
Recommended article: Algorithms – ESA 2004
Recommended article: Efficient and Simple Algorithms for Fault-Tolerant Spanners
Recommended article: Fast Constructions of Light-Weight Spanners for General Graphs
description: scientific article; zbMATH DE number 7362189