A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree

DOI10.4230/LIPIcs.ISAAC.2016.59zbMath1398.05204OpenAlexW2572905496MaRDI QIDQ4636543

Eunjin Oh, Hee-Kap Ahn

Publication date: 19 April 2018

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2016/6828/

zbMATH Keywords

shortcutsdiametertreesnetwork augmentation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Algorithms for radius-optimally augmenting trees in a metric space ⋮ Almost optimal algorithms for diameter-optimally augmenting trees ⋮ Finding diameter-reducing shortcuts in trees ⋮ Minimizing the continuous diameter when augmenting a geometric tree with a shortcut ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees ⋮ Algorithms for radius-optimally augmenting trees in a metric space ⋮ Unnamed Item ⋮ A linear-time algorithm for radius-optimally augmenting paths in a metric space ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees ⋮ A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees

This page was built for publication: A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree