Additive Tree Spanners

DOI10.1137/S0895480195295471zbMath1041.05024OpenAlexW2022046900MaRDI QIDQ4443141

Erich Prisner, Hoàng-Oanh Le, Dorothea Wagner, Dieter Kratsch, Haiko Müller

Publication date: 8 January 2004

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algorithmdistancespanning treechordal graphgraph spannerdistance-hereditary graphasteroidal triple-free graph

Mathematics Subject Classification ID

Related Items (20)

Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \) ⋮ Eccentricity Approximating Trees ⋮ Collective tree spanners in graphs with bounded parameters ⋮ Spanners for bounded tree-length graphs ⋮ Helly-gap of a graph and vertex eccentricities ⋮ Eccentricity approximating trees ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Tree spanners of bounded degree graphs ⋮ Collective additive tree spanners for circle graphs and polygonal graphs ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph ⋮ Tree \(t\)-spanners in outerplanar graphs via supply demand partition ⋮ Easy computation of eccentricity approximating trees ⋮ Combinatorial network abstraction by trees and distances ⋮ The zoo of tree spanner problems ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ On 2-detour subgraphs of the hypercube ⋮ Additive tree 2-spanners of permutation graphs ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle

This page was built for publication: Additive Tree Spanners