[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

A Note on Distance Approximating Trees in Graphs

Published: 01 August 2000 Publication History

Abstract

Let G= (V, E) be a connected graph endowed with the standard graph-metric dGand in which longest induced simple cycle has length (G). We prove that there exists a tree T= (V,F ) such that| dG(u, v) dT(u, v)| (G)2 + for all vertices u, v V, where = 1 if (G) = 4, 5 and = 2 otherwise. The case (G) = 3 (i.e., G is a chordal graph) has been considered in Brandst dt, Chepoi, and Dragan, (1999) J.Algorithms 30. The proof contains an efficient algorithm for determining such a treeT .

References

[1]
A. Brandstädt, V. Chepoi, F. Dragan, Distance approximating trees for chordal and dually chordal graphs, J. Algorithms, 30 (1999) 166-184.
[2]
E. Ghys, P. de la Harpe, Les Groupes Hyperboliques d¿après Mikhael Gromov, Prog. Math., 83 (1990).

Cited By

View all
  • (2020)Tree! I am no tree! I am a low dimensional hyperbolic embeddingProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3495796(845-856)Online publication date: 6-Dec-2020
  • (2018)On Weak Isomorphism of Rooted Vertex-Colored GraphsGraph-Theoretic Concepts in Computer Science10.1007/978-3-030-00256-5_22(266-278)Online publication date: 27-Jun-2018
  • (2017)Parameterized Approximation Algorithms for Some Location Problems in GraphsCombinatorial Optimization and Applications10.1007/978-3-319-71147-8_24(348-361)Online publication date: 16-Dec-2017
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image European Journal of Combinatorics
European Journal of Combinatorics  Volume 21, Issue 6
Aug. 2000
137 pages
ISSN:0195-6698
  • Editors:
  • M. Deza,
  • P. Rosensthiehl,
  • P. Cameron
Issue’s Table of Contents

Publisher

Academic Press Ltd.

United Kingdom

Publication History

Published: 01 August 2000

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 24 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Tree! I am no tree! I am a low dimensional hyperbolic embeddingProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3495796(845-856)Online publication date: 6-Dec-2020
  • (2018)On Weak Isomorphism of Rooted Vertex-Colored GraphsGraph-Theoretic Concepts in Computer Science10.1007/978-3-030-00256-5_22(266-278)Online publication date: 27-Jun-2018
  • (2017)Parameterized Approximation Algorithms for Some Location Problems in GraphsCombinatorial Optimization and Applications10.1007/978-3-319-71147-8_24(348-361)Online publication date: 16-Dec-2017
  • (2016)Metric tree-like structures in real-world networksNetworks10.1002/net.2163167:1(49-68)Online publication date: 1-Jan-2016
  • (2015)Finding four-node subgraphs in triangle timeProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722240(1671-1680)Online publication date: 4-Jan-2015
  • (2014)An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal GraphsAlgorithmica10.1007/s00453-013-9765-469:4(884-905)Online publication date: 1-Aug-2014
  • (2012)Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar GraphsDiscrete & Computational Geometry10.5555/3116263.311642447:1(187-214)Online publication date: 1-Jan-2012
  • (2010)Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphsProceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques10.5555/1886521.1886530(95-109)Online publication date: 1-Sep-2010
  • (2008)Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphsProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377687(59-68)Online publication date: 9-Jun-2008
  • (2007)Spanners for bounded tree-length graphsTheoretical Computer Science10.1016/j.tcs.2007.03.058383:1(34-44)Online publication date: 2-Sep-2007
  • Show More Cited By

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media