Distance Approximating Trees for Chordal and Dually Chordal Graphs

DOI10.1006/jagm.1998.0962zbMath0914.68148OpenAlexW2001231944MaRDI QIDQ4228290

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

Publication date: 2 February 1999

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.4457

zbMATH Keywords

chordal graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (27)

Tree spanners on chordal graphs: complexity and algorithms ⋮ Eccentricity Approximating Trees ⋮ A Faster Computation of All the Best Swap Edges of a Tree Spanner ⋮ New results on pairwise compatibility graphs ⋮ Eccentricity approximating trees ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ On the hyperbolicity constant of circular-arc graphs ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Tree spanners of bounded degree graphs ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs ⋮ Easy computation of eccentricity approximating trees ⋮ A distance approximating trees ⋮ An improved algorithm for computing all the best swap edges of a tree spanner ⋮ The intrinsic dimensionality of graphs ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ Collective Additive Tree Spanners of Homogeneously Orderable Graphs ⋮ Optimal tree 3-spanners in directed path graphs ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction ⋮ A note on distance approximating trees in graphs ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle ⋮ An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner ⋮ Fast Diameter Computation within Split Graphs

This page was built for publication: Distance Approximating Trees for Chordal and Dually Chordal Graphs