[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Distance Approximating Trees: Complexity and Algorithms

  • Conference paper
Algorithms and Complexity (CIAC 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3998))

Included in the following conference series:

Abstract

Let Δ≥ 1 and δ≥ 0 be real numbers. A tree T=(V,E′) is a distance (Δ,δ )–approximating tree of a graph G=(V,E) if d H (u,v) ≤ Δ  d G (u,v) + δ and d G (u,v) ≤ Δ  d H (u,v) + δ hold for every u,v∈ V. The distance (Δ,δ )-approximating tree problem asks for a given graph G to decide whether G has a distance (Δ,δ)-approximating tree. In this paper, we consider unweighted graphs and show that the distance (Δ,0)-approximating tree problem is NP-complete for any Δ≥ 5 and the distance (1,1)-approximating tree problem is polynomial time solvable.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bartal, Y.: Probabalistic approximation of metric spaces and its algorithmic applications. In: FOCS 1996, pp. 184–193 (1996)

    Google Scholar 

  2. Bartal, Y., Blum, A., Burch, C., Tomkins, A.: A polylog(n)competitive algorithm for metrical task systems. In: STOC 1997, pp. 711–719 (1997)

    Google Scholar 

  3. Barthélemy, J.-P., Guénoche, A.: Trees and Proximity Representations. Wiley, New York (1991)

    MATH  Google Scholar 

  4. Brandstädt, A., Chepoi, V., Dragan, F.F.: Distance Approximating Trees for Chordal and Dually Chordal Graphs. Journal of Algorithms 30, 166–184 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  5. Brandstädt, A., Dragan, F., Le, H.-O., Le, V.B.: Tree Spanners on Chordal Graphs: Complexity and Algorithms. Theor. Comput. Science 310, 329–354 (2004)

    Article  MATH  Google Scholar 

  6. Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Disc. Math. 8, 359–387 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  7. Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a Finite Metric by a Small Number of Tree Metrics. In: FOCS 1998, pp. 379–388 (1998)

    Google Scholar 

  8. Chepoi, V., Dragan, F.F.: A note on distance approximating trees in graphs. European Journal of Combinatorics 21, 761–766 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  9. Chew, L.P.: There are planar graphs almost as good as the complete graph. J. of Computer and System Sciences 39, 205–219 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  10. Emek, Y., Peleg, D.: Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs. In: SODA 2004, pp. 261–270 (2004)

    Google Scholar 

  11. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC 2003, pp. 448–455 (2003)

    Google Scholar 

  12. Feige, U.: Approximating the Bandwidth via Volume Respecting Embeddings. J. Comput. System Sci. 60, 510–539 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  13. Gupta, A.: Improved bandwidth approximation for trees and chordal graphs. Journal of Algorithms 40, 24–36 (2001)

    Article  MATH  Google Scholar 

  14. Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2, 135–158 (1973)

    Article  MathSciNet  Google Scholar 

  15. Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems, I: the p-centers. SIAM J. Appl. Math. 37, 513–538 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  16. Kratsch, D., Le, H.-O., Müller, H., Prisner, E., Wagner, D.: Additive tree spanners. SIAM J. Discrete Math. 17, 332–340 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  17. Krauthgamer, R., Lee, J.R.: The intrinsic dimensionality of graphs. In: STOC 2003, pp. 438–447 (2003)

    Google Scholar 

  18. Krauthgamer, R., Linial, N., Magen, A.: Metric Embedding – Beyond one-dimensional distortion. Discrete and Computational Geometry 31, 339–356 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  19. Liestman, A.L., Shermer, T.: Additive graph spanners. Networks 23, 343–364 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  20. Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some its algorithmic applications. Combinatorica 15, 215–245 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  21. McKee, T.A.: Personal communication to E. Prisner (1995)

    Google Scholar 

  22. Miller, G.L., Ramachandran, V.: A new graph triconnectivity algorithm and its parallelization. Combinatorica 12, 53–76 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  23. Peleg, D., Schäffer, A.A.: Graph Spanners. J. Graph Theory 13, 99–116 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  24. Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. In: PODC 1987, pp. 77–85 (1987)

    Google Scholar 

  25. Prisner, E.: Distance approximating spanning trees. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 499–510. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  26. Sneath, P.H.A., Sokal, R.R.: Numerical Taxonomy. W.H. Freeman, San Francisco (1973)

    MATH  Google Scholar 

  27. Swofford, D.L., Olsen, G.J.: Phylogeny reconstruction. In: Hillis, D.M., Moritz, C. (eds.) Molecular Systematics, pp. 411–501. Sinauer Associates Inc., Sunderland (1990)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Kent State University, Kent, OH, 44242, USA

    Feodor F. Dragan & Chenyu Yan

Authors
  1. Feodor F. Dragan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chenyu Yan
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Rome, ”Sapienza”, Italy

    Tiziana Calamoneri

  2. Computer Science Department, Sapienza University of Rome, Via Salaria, 113, 00198, Rome, Italy

    Irene Finocchi

  3. Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, via del Politecnico 1, 00133, Roma, Italy

    Giuseppe F. Italiano

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dragan, F.F., Yan, C. (2006). Distance Approximating Trees: Complexity and Algorithms. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds) Algorithms and Complexity. CIAC 2006. Lecture Notes in Computer Science, vol 3998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758471_26

Download citation

  • DOI: https://doi.org/10.1007/11758471_26

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-34375-2

  • Online ISBN: 978-3-540-34378-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation