Graph spanners
From MaRDI portal
Recommendations
- Spanners in sparse graphs
- Spanners in Sparse Graphs
- scientific article; zbMATH DE number 1301100
- scientific article; zbMATH DE number 434498
- Drawing graphs as spanners
- Drawing graphs as spanners
- Graph spanners: a tutorial review
- Additive graph spanners
- Spanning paths in graphs
- Spanners for directed transmission graphs
Cited in
(only showing first 100 items - show all)- On 2-detour subgraphs of the hypercube
- Region-fault tolerant geometric spanners
- Edge-disjoint spanners in tori
- Lower bounds on treespan
- Classes of graphs which approximate the complete Euclidean graph
- On sparse spanners of weighted graphs
- Edge-disjoint spanners of complete graphs and complete digraphs
- NP-completeness of minimum spanner problems
- Approximating Euclidean distances by small degree graphs
- Graph theoretical issues in computer networks
- Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
- Restrictions of minimum spanner problems
- Sparse hypercube 3-spanners
- On approximating planar metrics by tree metrics.
- New pairwise spanners
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
- (k,+)-distance-hereditary graphs
- Tree spanners on chordal graphs: complexity and algorithms
- The geometry of graphs and some of its algorithmic applications
- Degree-constrained spanners for multidimensional grids
- Spanners of bounded degree graphs
- Computing the greedy spanner in near-quadratic time
- Making asynchronous distributed computations robust to noise
- Preprocess, set, query!
- Graph spanners: a tutorial review
- A fast algorithm for source-wise round-trip spanners
- Temporal cliques admit sparse spanners
- Sparsification lower bound for linear spanners in directed graphs
- Local geometric spanners
- Constructing light spanners deterministically in near-linear time
- Learning to sparsify travelling salesman problem instances
- Lasserre integrality gaps for graph spanners and related problems
- Minimum \(t\)-spanners on subcubic graphs
- Parameterized complexity of directed spanner problems
- Covering metric spaces by few trees
- Demand-aware network designs of bounded degree
- The sparsest additive spanner via multiple weighted BFS trees
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Measuring sample quality with diffusions
- Local algorithms for sparse spanning graphs
- Tree-decompositions with bags of small diameter
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Spanners for bounded tree-length graphs
- Deterministic improved round-trip spanners
- Distributed distance computation and routing with small messages
- Activity preserving graph simplification
- Edge-disjoint spanners in Cartesian products of graphs
- Self-spanner graphs
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Source-wise round-trip spanners
- On additive spanners in weighted graphs with local error
- Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
- Faster cut sparsification of weighted graphs
- Minimum spanners of butterfly graphs
- Spanners of de Bruijn and Kautz graphs
- Spanners of underlying graphs of iterated line digraphs
- Rumor spreading with no dependence on conductance
- Improved approximation for the directed spanner problem
- Steiner transitive-closure spanners of low-dimensional posets
- Computing graph spanners in small memory: fault-tolerance and streaming
- Graphs with minimum spanner (G)2-1
- Computing minimum dilation spanning trees in geometric graphs
- Models and algorithms for network reduction
- Simple distributed spanners in dense congest networks
- Distributed distance-bounded network design through distributed convex programming
- Small stretch pairwise spanners and approximate D-preservers
- Computing the Greedy Spanner in Near-Quadratic Time
- Spanners in Sparse Graphs
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Approximating Shortest Paths in Graphs
- ON SPANNERS OF GEOMETRIC GRAPHS
- Spanders: distributed spanning expanders
- Steiner transitive-closure spanners of low-dimensional posets
- Sparse reliable graph backbones
- scientific article; zbMATH DE number 1301100 (Why is no real title available?)
- Optimal tree 3-spanners in directed path graphs
- Spanners in graphs of bounded degree
- scientific article; zbMATH DE number 2014474 (Why is no real title available?)
- Collective additive tree spanners for circle graphs and polygonal graphs
- Light graphs with small routing cost
- A hierarchy of lower bounds for sublinear additive spanners
- Optimal network design with end-to-end service requirements
- Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
- Multipath spanners via fault-tolerant spanners
- Transitive-closure spanners: a survey
- The greedy spanner is existentially optimal
- Making Asynchronous Distributed Computations Robust to Channel Noise
- Distance-Preserving Graph Contractions
- Distributed spanner approximation
- scientific article; zbMATH DE number 7376014 (Why is no real title available?)
- Generating sparse spanners for weighted graphs
- Generating sparse 2—spanners
- Angle-constrained spanners with angle at least \(\pi/3\)
- Constructing Light Spanners Deterministically in Near-Linear Time
- Optimal (Euclidean) Metric Compression
- Lossless prioritized embeddings
- Local computation algorithms for spanners
- Congested clique algorithms for graph spanners
- The Sparsest Additive Spanner via Multiple Weighted BFS Trees
- Covering Metric Spaces by Few Trees
This page was built for publication: Graph spanners
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3826599)
