Abstract
We consider the problem of augmenting a graph with \(n\) vertices embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present an exact algorithm for the cases when the input graph is a path that runs in \(O(n \log ^3 n)\) time. We also present an algorithm that computes a \((1+\varepsilon )\)-approximation in \(O(n + 1/\varepsilon ^3)\) time for paths in \({\mathbb {R}}^{d}\), where \(d\) is a constant.
The research on this topic has been initiated during the Korean Workshop on Computational Geometry 2014 (KW2014)
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
Alon, N., Gyárfás, A., Ruszinkó, M.: Decreasing the diameter of bounded degree graphs. Journal of Graph Theory 35, 161–172 (1999)
Bilò, D., Gualà, L., Proietti, G.: Improved approximability and non-approximability results for graph diameter decreasing problems. Theoretical Computer Science 417, 12–22 (2012)
Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to \(k\)-nearest-neighbors and \(n\)-body potential fields. Journal of the ACM 42, 67–90 (1995)
Chepoi, V., Vaxès, Y.: Augmenting trees to meet biconnectivity and diameter constraints. Algorithmica 33(2), 243–262 (2002)
Chung, F.R.K., Garey, M.R.: Diameter bounds for altered graphs. Journal of Graph Theory 8(4), 511–534 (1984)
Dodis, Y., Khanna, S.: Designing networks with bounded pairwise distance. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 750–759 (1999)
Erdős, P., Gyárfás, A., Ruszinkó, M.: How to decrease the diameter of triangle-free graphs. Combinatorica 18(4), 493–501 (1998)
Farshi, M., Giannopoulos, P., Gudmundsson, J.: Improving the stretch factor of a geometric network by edge augmentation. SIAM Journal on Computing 38(1), 226–240 (2005)
Frati, F., Gaspers, S., Gudmundsson, J., Mathieson, L.: Augmenting graphs to minimize the diameter. Algorithmica, 1–16 (2014)
Gao, Y., Hare, D.R., Nastos, J.: The parametric complexity of graph diameter augmentation. Discrete Applied Mathematics 161(10–11), 1626–1631 (2013)
Ishii, T.: Augmenting outerplanar graphs to meet diameter requirements. Journal of Graph Theory 74, 392–416 (2013)
Kapoor, S., Sarwat, M.: Bounded-diameter minimum-cost graph problems. Theory of Computing Systems 41(4), 779–794 (2007)
Li, C.-L., McCormick, S.T., 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)
Rutter, I., Wolff, A.: Augmenting the connectivity of planar and geometric graphs. Journal of Graph Algorithms and Applications 16(2), 599–628 (2012)
Schoone, A.A., Bodlaender, H.L., van Leeuwen, J.: Diameter increase caused by edge deletion. Journal of Graph Theory 11, 409–427 (1997)
Wulff-Nilsen, C.: Computing the dilation of edge-augmented graphs in metric spaces. Computational Geometry - Theory and Applications 43(2), 68–72 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Große, U., Gudmundsson, J., Knauer, C., Smid, M., Stehn, F. (2015). Fast Algorithms for Diameter-Optimally Augmenting Paths. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_55
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_55
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)