Easy computation of eccentricity approximating trees

DOI10.1016/J.DAM.2019.01.006MaRDI QIDQ1741520zbMATH OpenOpenAlexFDO

Authors 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) Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Recommendations

• Eccentricity approximating trees (extended abstract)
• Eccentricity approximating trees
• Eccentricity-approximating trees in chordal graphs
• An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
• Fast approximation of eccentricities and distances in hyperbolic graphs

Cites work

• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 5228 (Why is no real title available?)
• Additive Tree Spanners
• Algorithms and Computation
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Collective tree spanners of graphs
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Eccentricity approximating trees
• Eccentricity-approximating trees in chordal graphs
• Fast approximation of centrality and distances in hyperbolic graphs
• Finding a central vertex in an HHD-free graph
• Graph theory
• Graph-Theoretic Concepts in Computer Science
• Graphs with all diametral paths through distant central nodes

Cited in

(6)

• An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Eccentricity approximating trees
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• Eccentricity approximating trees (extended abstract)
• $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities

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

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