Additive graph spanners
A spanning subgraph \(S=(V,E')\) of a connected simple graph \(G=(V,E)\) is a \(f(x)\)-spanner if for any pair of nodes \(u\) and \(v\), \(d_ S(u,v) \leq f \bigl( d_ G(u,v) \bigr)\) where \(d_ G\) and \(d_ S\) are the usual distance functions in graphs \(G\) and \(S\), respectively. We are primarily interested in \((t+x)\)-spanners, which we refer to as additive spanners. We construct low-degree additive spanners for \(X\)- trees, pyramids and multidimensional grids. We prove, for arbitrary \(t>0\), that to determine whether a given graph \(G\) has an additive spanner with no more than \(m\) edges is \(NP\)-complete.
- Additive Spanners for Circle Graphs and Polygonal Graphs
- Additive spanners for k-chordal graphs
- Sparse additive spanners for bounded tree-length graphs
- Additive Tree Spanners
- Graph spanners
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Spanners in Sparse Graphs
- Spanners in sparse graphs
- Collective additive tree spanners for circle graphs and polygonal graphs
- On additive spanners in weighted graphs with local error
- On 2-detour subgraphs of the hypercube
- Edge-disjoint spanners in tori
- Edge-disjoint spanners of complete graphs and complete digraphs
- Restrictions of minimum spanner problems
- Degree-constrained spanners for multidimensional grids
- Graph spanners: a tutorial review
- Sparsification lower bound for linear spanners in directed graphs
- Parameterized complexity of directed spanner problems
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
- Edge-disjoint spanners in Cartesian products of graphs
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Spanners of de Bruijn and Kautz graphs
- Spanners of underlying graphs of iterated line digraphs
- Network flow spanners
- Computing graph spanners in small memory: fault-tolerance and streaming
- Additive tree 2-spanners of permutation graphs
- Graph spanners
- Additive Tree Spanners
- Collective additive tree spanners for circle graphs and polygonal graphs
- Distance-Preserving Graph Contractions
- Distance approximating spanning trees
- Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
- Distance-Preserving Graph Contractions
- Additive Spanners for Circle Graphs and Polygonal Graphs
- Collective Additive Tree Spanners of Homogeneously Orderable Graphs
- Parameterized Complexity of Directed Spanner Problems.
- Iterated local search with two strategies in the acceptance criterion for the tree t-spanner problem
- Bounded degree spanners of the hypercube
- Graph spanners in the streaming model: An experimental study
- Small stretch ( , )-spanners in the streaming model
- Collective tree spanners in graphs with bounded parameters
- Interaction graphs: additives
- A distance approximating trees
- Combinatorial network abstraction by trees and distances
This page was built for publication: Additive graph spanners
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5289379)
