Graph spanners
From MaRDI portal
Publication:3826599
DOI10.1002/jgt.3190130114zbMath0673.05059OpenAlexW4245082111MaRDI QIDQ3826599
Alejandro A. Schäffer, David Peleg
Publication date: 1989
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.3190130114
Related Items
Sparse hop spanners for unit disk graphs ⋮ Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling ⋮ Spanners of de Bruijn and Kautz graphs ⋮ Spanners of underlying graphs of iterated line digraphs ⋮ On resilient graph spanners ⋮ On the dilation spectrum of paths, cycles, and trees ⋮ Tree spanners on chordal graphs: complexity and algorithms ⋮ Graph spanners in the streaming model: An experimental study ⋮ Tree-decompositions with bags of small diameter ⋮ Small stretch \((\alpha ,\beta )\)-spanners in the streaming model ⋮ Source-wise round-trip spanners ⋮ Light graphs with small routing cost ⋮ Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ The geometry of graphs and some of its algorithmic applications ⋮ Collective tree spanners in graphs with bounded parameters ⋮ Models and algorithms for network reduction ⋮ Spanners for bounded tree-length graphs ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Parameterized complexity of directed spanner problems ⋮ Computing Minimum Dilation Spanning Trees in Geometric Graphs ⋮ Restrictions of minimum spanner problems ⋮ Geometric spanners with applications in wireless networks ⋮ Covering metric spaces by few trees ⋮ Degree-constrained spanners for multidimensional grids ⋮ A PTAS for the sparsest 2-spanner of 4-connected planar triangulations ⋮ Networks with small stretch number ⋮ Deterministic improved round-trip spanners ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ On additive spanners in weighted graphs with local error ⋮ Spanders: distributed spanning expanders ⋮ Steiner transitive-closure spanners of low-dimensional posets ⋮ Demand-aware network designs of bounded degree ⋮ Computing the greedy spanner in linear space ⋮ Distributed distance computation and routing with small messages ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ New pairwise spanners ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Sparse reliable graph backbones ⋮ Computing the Greedy Spanner in Near-Quadratic Time ⋮ Spanners of bounded degree graphs ⋮ Rumor Spreading with No Dependence on Conductance ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Optimal Network Design with End-to-End Service Requirements ⋮ Faster cut sparsification of weighted graphs ⋮ Activity preserving graph simplification ⋮ On dynamic shortest paths problems ⋮ Collective additive tree spanners for circle graphs and polygonal graphs ⋮ Computing the greedy spanner in near-quadratic time ⋮ Spanners in sparse graphs ⋮ Minimum spanners of butterfly graphs ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Classes of graphs which approximate the complete Euclidean graph ⋮ Angle-constrained spanners with angle at least \(\pi/3\) ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Steiner Transitive-Closure Spanners of Low-Dimensional Posets ⋮ On sparse spanners of weighted graphs ⋮ Combinatorial network abstraction by trees and distances ⋮ Multipath Spanners via Fault-Tolerant Spanners ⋮ Distribution-sensitive construction of the greedy spanner ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Streaming algorithm for graph spanners-single pass and constant processing time per edge ⋮ Edge-disjoint spanners in Cartesian products of graphs ⋮ Making asynchronous distributed computations robust to noise ⋮ Approximate shortest paths guided by a small index ⋮ Optimal spanners for axis-aligned rectangles ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ Transitive-Closure Spanners: A Survey ⋮ Preprocess, set, query! ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Graph spanners: a tutorial review ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ Approximating Shortest Paths in Graphs ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Measuring sample quality with diffusions ⋮ Temporal cliques admit sparse spanners ⋮ ON SPANNERS OF GEOMETRIC GRAPHS ⋮ Optimal tree 3-spanners in directed path graphs ⋮ Local algorithms for sparse spanning graphs ⋮ On 2-detour subgraphs of the hypercube ⋮ COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING ⋮ Region-fault tolerant geometric spanners ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ Edge-disjoint spanners in tori ⋮ Local geometric spanners ⋮ (\(k,+\))-distance-hereditary graphs ⋮ Sparse hypercube 3-spanners ⋮ Constructing light spanners deterministically in near-linear time ⋮ Self-spanner graphs ⋮ Edge-disjoint spanners of complete graphs and complete digraphs ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle ⋮ NP-completeness of minimum spanner problems ⋮ On approximating planar metrics by tree metrics. ⋮ Approximating Euclidean distances by small degree graphs ⋮ Graph theoretical issues in computer networks ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming ⋮ Learning to sparsify travelling salesman problem instances ⋮ Lasserre integrality gaps for graph spanners and related problems ⋮ Generating sparse spanners for weighted graphs ⋮ Generating sparse 2—spanners ⋮ Additive Spanners for Circle Graphs and Polygonal Graphs ⋮ Unnamed Item ⋮ Optimal (Euclidean) Metric Compression ⋮ Lossless Prioritized Embeddings ⋮ Reliable Spanners for Metric Spaces ⋮ Improved weighted additive spanners ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Unnamed Item ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Online Spanners in Metric Spaces ⋮ Unnamed Item ⋮ Universal routing schemes ⋮ Making Asynchronous Distributed Computations Robust to Channel Noise ⋮ Compact and localized distributed data structures ⋮ Parameterized Complexity of Directed Spanner Problems. ⋮ Small hop-diameter sparse spanners for doubling metrics ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Graphs with bounded induced distance ⋮ Tree spanners in planar graphs ⋮ Independent tree spanners: Fault-tolerant spanning trees with constant distance guarantees ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ Covering Metric Spaces by Few Trees ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Congested Clique Algorithms for Graph Spanners ⋮ Temporal Cliques Admit Sparse Spanners ⋮ A General Framework for Graph Sparsification ⋮ Distance-Preserving Graph Contractions ⋮ Distance-Preserving Subgraphs of Interval Graphs ⋮ Distributed Spanner Approximation ⋮ Distance-Preserving Graph Contractions ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ The Topological Fortress of Termites
Cites Work
