Distance approximating trees for chordal and dually chordal graphs (extended abstract)

DOI10.1007/3-540-63397-9_7MaRDI QIDQ826072zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Feodor F. Dragan, Andreas Brandstädt

Publication date 20 December 2021

Full work available at URL https://doi.org/10.1007/3-540-63397-9_7

zbMATH Keywords

line graphspanning subgraphspanning treeSteiner treechordal graph

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Recommendations

• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
• Distance approximating spanning trees
• Distance approximating trees in graphs
• Tree spanners on chordal graphs: complexity and algorithms

Cited in

(7)

• A note on distance approximating trees in graphs
• Additive Tree Spanners
• An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
• Duality between distant point and median of a tree network space
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Distance approximating trees in graphs
• Distance approximating spanning trees

This page was built for publication: Distance approximating trees for chordal and dually chordal graphs (extended abstract)

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