Easy computation of eccentricity approximating trees

DOI10.1016/j.dam.2019.01.006zbMath1409.05052OpenAlexW2914168686MaRDI QIDQ1741520

Guillaume Ducoffe

Publication date: 3 May 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.01.006

zbMATH Keywords

complexitygraph algorithmsshortest-path treeeccentricity-approximating tree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Eccentricity terrain of \(\delta\)-hyperbolic graphs ⋮ An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs with all diametral paths through distant central nodes
• Finding a central vertex in an HHD-free graph
• Eccentricity-approximating trees in chordal graphs
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Fast approximation of centrality and distances in hyperbolic graphs
• Eccentricity approximating trees
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Additive Tree Spanners
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Collective tree spanners of graphs
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation

This page was built for publication: Easy computation of eccentricity approximating trees