Additive Tree Spanners
From MaRDI portal
Publication:4443141
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
algorithmdistancespanning treechordal graphgraph spannerdistance-hereditary graphasteroidal triple-free graph
Graph theory (including graph drawing) in computer science (68R10) Discrete location and assignment (90B80) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
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
