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

DOI10.1007/3-540-63397-9_7zbMATH Open1477.68208OpenAlexW1621295142MaRDI QIDQ826072FDOQ826072

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

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

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)

Cited In (7)

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

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)