2026-07-25T18:31:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6828 2024-03-06T10:38:59Z ddc:004 open_access

A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree Oh, Eunjin Ahn, Hee-Kap Network Augmentation Shortcuts Diameter Trees We consider the problem of finding a shortcut connecting two vertices of a graph that minimizes the diameter of the resulting graph. We present an O(n^2 log^3 n)-time algorithm using linear space for the case that the input graph is a tree consisting of n vertices. Additionally, we present an O(n^2 log^3 n)-time algorithm using linear space for a continuous version of this problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eunjin Oh and Hee-Kap Ahn 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.59 urn:nbn:de:0030-drops-68283 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.59 eng https://creativecommons.org/licenses/by/3.0/legalcode