Abstract
We augment a tree \(T\) with a shortcut \(pq\) to minimize the largest distance between any two points along the resulting augmented tree \(T+pq\). We study this problem in a continuous and geometric setting where \(T\) is a geometric tree in the Euclidean plane, a shortcut is a line segment connecting any two points along the edges of \(T\), and we consider all points on \(T+pq\) (i.e., vertices and points along edges) when determining the largest distance along \(T+pq\). The continuous diameter is the largest distance between any two points along edges. We establish that a single shortcut is sufficient to reduce the continuous diameter of a geometric tree \(T\) if and only if the intersection of all diametral paths of \(T\) is neither a line segment nor a point. We determine an optimal shortcut for a geometric tree with \(n\) straight-line edges in \(O(n \log n)\) time.
This work was partially supported by NSERC and FQRNT.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cáceres, J., Garijo, D., González, A., Márquez, A., Puertas, M.L., Ribeiro, P.: Shortcut Sets for Plane Euclidean Networks. Electron. Notes Discrete Math. 54, 163–168 (2016)
Chepoi, V., Vaxès, Y.: Augmenting Trees to Meet Biconnectivity and Diameter Constraints. Algorithmica 33(2), 243–262 (2002)
De Carufel, J.L., Grimm, C., Maheshwari, A., Smid, M.: Minimizing the continuous diameter when augmenting paths and cycles with shortcuts. In: SWAT 2016, pp. 27:1–27:14 (2016)
Farshi, M., Giannopoulos, P., Gudmundsson, J.: Improving the Stretch Factor of a Geometric Network by Edge Augmentation. SIAM J. Comp. 38(1), 226–240 (2008)
Frati, F., Gaspers, S., Gudmundsson, J., Mathieson, L.: Augmenting Graphs to Minimize the Diameter. Algorithmica 72(4), 995–1010 (2015)
Gao, Y., Hare, D.R., Nastos, J.: The Parametric Complexity of Graph Diameter Augmentation. Discrete Appl. Math. 161(10–11), 1626–1631 (2013)
Große, U., Gudmundsson, J., Knauer, C., Smid, M., Stehn, F.: Fast algorithms for diameter-optimally augmenting paths. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 678–688. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47672-7_55
Große, U., Gudmundsson, J., Knauer, C., Smid, M., Stehn, F.: Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees (2016). arXiv:1607.05547
Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research 12(3), 450–459 (1964)
Li, C.L., McCormick, S., Simchi-Levi, D.: On the Minimum-Cardinality-Bounded-Diameter and the Bounded-Cardinality-Minimum-Diameter Edge Addition Problems. Operations Research Letters 11(5), 303–308 (1992)
Luo, J., Wulff-Nilsen, C.: Computing best and worst shortcuts of graphs embedded in metric spaces. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 764–775. Springer, Heidelberg (2008). doi:10.1007/978-3-540-92182-0_67
Oh, E., Ahn, H.K.: A near-optimal algorithm for finding an optimal shortcut of a tree. In: ISAAC 2016, pp. 59:1–59:12 (2016)
Schoone, A.A., Bodlaender, H.L., van Leeuwen, J.: Diameter Increase Caused by Edge Deletion. Journal of Graph Theory 11(3), 409–427 (1987)
Yang, B.: Euclidean Chains and their Shortcuts. Theor. Comput. Sci. 497, 55–67 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
De Carufel, JL., Grimm, C., Schirra, S., Smid, M. (2017). Minimizing the Continuous Diameter When Augmenting a Tree with a Shortcut. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-62127-2_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62126-5
Online ISBN: 978-3-319-62127-2
eBook Packages: Computer ScienceComputer Science (R0)