scientific article; zbMATH DE number 7238981
From MaRDI portal
Publication:5116490
DOI10.4230/LIPICS.SWAT.2018.26zbMATH Open1477.68230arXiv1802.06271MaRDI QIDQ5116490FDOQ5116490
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?)
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?)
- All-Pairs Almost Shortest Paths
- Low distortion spanners
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- Additive spanners and (Ξ±, Ξ²)-spanners
- Sparse Sourcewise and Pairwise Distance Preservers
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- New Additive Spanners
- Testing subgraphs in large graphs
- Shortcutting Planar Digraphs
- The convex hull of the integer points in a large ball
- The 4/3 Additive Spanner Exponent Is Tight
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Additive Spanners: A Simple Construction
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- Better Distance Preservers and Additive Spanners
- Linear Size Distance Preservers
- Very Sparse Additive Spanners and Emulators
- Nearly work-efficient parallel algorithm for digraph reachability
Cited In (7)
- Graph spanners: a tutorial review
- New Results on Linear Size Distance Preservers
- Error Amplification for Pairwise Spanner Lower Bounds
- Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
- Sparsification lower bound for linear spanners in directed graphs
- Improved Guarantees for Vertex Sparsification in Planar Graphs
- Title not available (Why is that?)
Recommendations
- Title not available (Why is that?) π π
- Fast approximation algorithms for the diameter and radius of sparse graphs π π
- Lower bounds for computing geometric spanners and approximate shortest paths π π
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS π π
- Lower bound for sparse Euclidean spanners π π
- Efficient Algorithms for Constructing Very Sparse Spanners and Emulators π π
- Efficient Algorithms for Constructing Very Sparse Spanners and Emulators π π
- Lowest-degree \(k\)-spanner: approximation and hardness π π
- Sparsification lower bound for linear spanners in directed graphs π π
- Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts π π
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)
