scientific article; zbMATH DE number 7238981

DOI10.4230/LIPICS.SWAT.2018.26MaRDI QIDQ5116490zbMATH OpenFDO

Authors Shang-En Huang, Seth Pettie

Publication date 25 August 2020

Full work available at URL https://arxiv.org/abs/1802.06271

zbMATH Keywords

emulatorsadditive spannersshortcutting directed graphs

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 512931 (Why is no real title available?)
• scientific article; zbMATH DE number 2079397 (Why is no real title available?)
• $(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
• Error Amplification for Pairwise Spanner Lower Bounds
• Near-optimal distance emulator for planar graphs
• 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)