New Additive Spanners

From MaRDI portal
Publication:5741744

DOI10.1137/1.9781611973105.36zbMath1412.68165OpenAlexW4214510568MaRDI QIDQ5741744

Shiri Chechik

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973105.36




Related Items (27)

On resilient graph spannersSource-wise round-trip spannersSmall Stretch Pairwise Spanners and Approximate $D$-PreserversA Hierarchy of Lower Bounds for Sublinear Additive SpannersDeterministic improved round-trip spannersOn additive spanners in weighted graphs with local errorCommunication-efficient distributed graph clustering and sparsification under duplication modelsVertex fault tolerant additive spannersImproved weighted additive spannersNew pairwise spannersMulti-priority graph sparsificationFault tolerant approximate BFS structures with additive stretchLower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing ShortcutsBypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise SpannersDistributed construction of purely additive spannersGraph spanners: a tutorial reviewNP-hardness and fixed-parameter tractability of the minimum spanner problemA fast algorithm for source-wise round-trip spannersFault-tolerant approximate shortest-path treesUnnamed ItemSparsification lower bound for linear spanners in directed graphsA note on distance-preserving graph sparsificationApproximate distance oracles with improved stretch for sparse graphsMultiple-edge-fault-tolerant approximate shortest-path treesBounded degree spanners of the hypercubeToward Tight Approximation Bounds for Graph Diameter and EccentricitiesFault tolerant additive and \((\mu, \alpha)\)-spanners




This page was built for publication: New Additive Spanners