scientific article; zbMATH DE number 7238981
From MaRDI portal
Publication:5116490
DOI10.4230/LIPICS.SWAT.2018.26zbMATH Open1477.68230MaRDI QIDQ5116490FDOQ5116490
Authors: Shang-En Huang, Seth Pettie 
Publication date: 25 August 2020
Full work available at URL: https://arxiv.org/abs/1802.06271
Title of this publication is not available (Why is that?)
Recommendations
- Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
- Efficient algorithms for constructing very sparse spanners and emulators
- Efficient algorithms for constructing very sparse spanners and emulators
- Lower bound for sparse Euclidean spanners
- Sparsification lower bound for linear spanners in directed graphs
- Lower bounds for computing geometric spanners and approximate shortest paths
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- An optimal-time construction of sparse Euclidean spanners with tiny diameter
- Lowest-degree \(k\)-spanner: approximation and hardness
- Fast approximation algorithms for the diameter and radius of sparse graphs
Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- Additive spanners and \(({\alpha}, {\beta})\)-spanners
- Additive spanners: a simple construction
- All-Pairs Almost Shortest Paths
- Better distance preservers and additive spanners
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Linear size distance preservers
- Low distortion spanners
- Nearly work-efficient parallel algorithm for digraph reachability
- New additive spanners
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- Shortcutting Planar Digraphs
- Sparse Sourcewise and Pairwise Distance Preservers
- Testing subgraphs in large graphs
- The 4/3 additive spanner exponent is tight
- The convex hull of the integer points in a large ball
- Very sparse additive spanners and emulators
Cited In (9)
- Graph spanners: a tutorial review
- Improved guarantees for vertex sparsification in planar graphs
- A hierarchy of lower bounds for sublinear additive spanners
- Near-optimal distance emulator for planar graphs
- Error Amplification for Pairwise Spanner Lower Bounds
- New results on linear size distance preservers
- Nearly work-efficient parallel algorithm for digraph reachability
- Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
- Sparsification lower bound for linear spanners in directed graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116490)
