World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees by:2 (Source: Crossref)

    We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(nlog3n) time, and (ii) the input graph is a tree, running in O(n2logn) time. We also present an algorithm for paths that computes a (1+𝜀)-approximation in O(n+1/𝜀3) time.

    Communicated by Marek Chrobak


    • 1. N. Alon, A. Gyárfás and M. Ruszinkó, Decreasing the diameter of bounded degree graphs, Journal of Graph Theory 35 (1999) 161–172. Crossref, ISIGoogle Scholar
    • 2. M. D. Berg, O. Cheong, M. V. Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications (Springer-Verlag TELOS, Santa Clara, CA, USA, 2008). CrossrefGoogle Scholar
    • 3. D. Bilò, L. Gualà and G. Proietti, Improved approximability and non-approximability results for graph diameter decreasing problems, Theoretical Computer Science 417 (2012) 12–22. Crossref, ISIGoogle Scholar
    • 4. J.-L. D. Carufel, C. Grimm, A. Maheshwari and M. Smid, Minimizing the continuous diameter when augmenting paths and cycles with shortcuts, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) 53 (2016), pp. 27:1–27:14. Google Scholar
    • 5. V. Chepoi and Y. Vaxès, Augmenting trees to meet biconnectivity and diameter constraints, Algorithmica 33(2) (2002) 243–262. Crossref, ISIGoogle Scholar
    • 6. F. R. K. Chung and M. R. Garey, Diameter bounds for altered graphs, Journal of Graph Theory 8(4) (1984) 511–534. Crossref, ISIGoogle Scholar
    • 7. T. H. Cormen, C. Stein, R. L. Rivest and C. E. Leiserson, Introduction to Algorithms, 1st edn. (MIT Press and McGraw-Hill, 1990). Google Scholar
    • 8. J.-L. De Carufel, C. Grimm, S. Schirra and M. Smid, Minimizing the continuous diameter when augmenting a tree with a shortcut, Algorithms and Data Structures, eds. F. EllenA. KolokolovaJ.-R. Sack (Springer International Publishing, Cham, 2017), pp. 301–312. CrossrefGoogle Scholar
    • 9. Y. Dodis and S. Khanna, Designing networks with bounded pairwise distance, Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), (1999), pp. 750–759. Google Scholar
    • 10. P. Erdős, A. Gyárfás and M. Ruszinkó, How to decrease the diameter of triangle-free graphs, Combinatorica 18(4) (1998) 493–501. Crossref, ISIGoogle Scholar
    • 11. M. Farshi, P. Giannopoulos and J. Gudmundsson, Improving the stretch factor of a geometric network by edge augmentation, SIAM Journal on Computing 38(1) (2005) 226–240. Crossref, ISIGoogle Scholar
    • 12. F. Frati, S. Gaspers, J. Gudmundsson and L. Mathieson, Augmenting graphs to minimize the diameter, Algorithmica (2014) 1–16. ISIGoogle Scholar
    • 13. Y. Gao, D. R. Hare and J. Nastos, The parametric complexity of graph diameter augmentation, Discrete Applied Mathematics 161(10–11) (2013) 1626–1631. Crossref, ISIGoogle Scholar
    • 14. U. Große, J. Gudmundsson, C. Knauer, M. Smid and F. Stehn, Fast algorithms for diameter-optimally augmenting paths, Automata, Languages, and Programming, eds. M. M. HalldórssonK. IwamaN. KobayashiB. Speckmann (Springer, Berlin, Heidelberg, 2015), pp. 678–688. CrossrefGoogle Scholar
    • 15. T. Ishii, Augmenting outerplanar graphs to meet diameter requirements, Journal of Graph Theory 74 (2013) 392–416. Crossref, ISIGoogle Scholar
    • 16. S. Kapoor and M. Sarwat, Bounded-diameter minimum-cost graph problems, Theory of Computing Systems 41(4) (2007) 779–794. Crossref, ISIGoogle Scholar
    • 17. C.-L. Li, S. T. McCormick and D. Simchi-Levi, On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems, Operations Research Letters 11(5) (1992) 303–308. Crossref, ISIGoogle Scholar
    • 18. J. Luo and C. Wulff-Nilsen, Computing best and worst shortcuts of graphs embedded in metric spaces, 19th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, (Springer, 2008). Google Scholar
    • 19. N. Megiddo, Combinatorial optimization with rational objective functions, Math. Oper. Res. 4 (1979) 414–424. CrossrefGoogle Scholar
    • 20. N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms, Journal of the ACM 30(4) (1983) 852–865. Crossref, ISIGoogle Scholar
    • 21. E. Oh and H.-K. Ahn, A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree, 27th International Symposium on Algorithms and Computation (ISAAC 2016), ed. S.-H. Hong, Leibniz International Proceedings in Informatics (LIPIcs) 64, (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016), pp. 59:1–59:12. Google Scholar
    • 22. I. Rutter and A. Wolff, Augmenting the connectivity of planar and geometric graphs, Journal of Graph Algorithms and Applications 16(2) (2012) 599–628. CrossrefGoogle Scholar
    • 23. A. A. Schoone, H. L. Bodlaender and J. van Leeuwen, Diameter increase caused by edge deletion, Journal of Graph Theory 11 (1997) 409–427. Crossref, ISIGoogle Scholar
    • 24. R. van Oostrum and R. C. Veltkamp, Parametric search made practical, Computational Geometry 28(2) (2004) 75–88. Crossref, ISIGoogle Scholar
    • 25. H. Wang, An improved algorithm for diameter-optimally augmenting paths in a metric space, Algorithms and Data Structures, eds. F. EllenA. KolokolovaJ.-R. Sack (Springer International Publishing, Cham, 2017), pp. 545–556. CrossrefGoogle Scholar
    • 26. C. Wulff-Nilsen, Computing the dilation of edge-augmented graphs in metric spaces, Computational Geometry — Theory and Applications 43(2) (2010) 68–72. Crossref, ISIGoogle Scholar
    • 27. B. Yang, Euclidean chains and their shortcuts, Theoretical Computer Science 497 (2013) 55–67. Crossref, ISIGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science