Additive Tree Spanners

DOI10.1137/S0895480195295471MaRDI QIDQ4443141zbMATH OpenOpenAlexFDO

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

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

distancealgorithmspanning treeasteroidal triple-free graphchordal graphdistance-hereditary graphgraph spanner

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Discrete location and assignment (90B80)

Recommendations

• Additive tree 2-spanners of permutation graphs
• Additive graph spanners
• Distance approximating trees for chordal and dually chordal graphs (extended abstract)
• Structural Information and Communication Complexity
• scientific article; zbMATH DE number 2011848

Cited in

(26)

• The zoo of tree spanner problems
• Tree \(t\)-spanners in outerplanar graphs via supply demand partition
• Eccentricity approximating trees
• Easy computation of eccentricity approximating trees
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Collective tree spanners in graphs with bounded parameters
• Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)
• Additivity in minimum cost spanning tree problems
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Additive graph spanners
• Eccentricity approximating trees (extended abstract)
• Distance approximating spanning trees
• Combinatorial network abstraction by trees and distances
• Collective additive tree spanners for circle graphs and polygonal graphs
• Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
• Tree spanners of bounded degree graphs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Spanners for bounded tree-length graphs
• Helly-gap of a graph and vertex eccentricities
• Structural Information and Communication Complexity
• scientific article; zbMATH DE number 4145711 (Why is no real title available?)
• Additive tree 2-spanners of permutation graphs
• On 2-detour subgraphs of the hypercube
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• Bounded-diameter tree-decompositions
• A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph

This page was built for publication: Additive Tree Spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4443141)