An improved algorithm for diameter-optimally augmenting paths in a metric space

DOI10.1016/j.comgeo.2018.06.004zbMath1443.68209arXiv1608.04456OpenAlexW3023988220MaRDI QIDQ5915544

Haitao Wang

Publication date: 31 October 2018

Published in: Lecture Notes in Computer Science, Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.04456

zbMATH Keywords

metric spacediameterpath graphsaugmenting pathsminimizing diameter

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

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

Cites Work

• Augmenting graphs to minimize the diameter
• Improved approximability and non-approximability results for graph diameter decreasing problems
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• The parametric complexity of graph diameter augmentation
• Augmenting Outerplanar Graphs to Meet Diameter Requirements
• Fast Algorithms for Finding Nearest Common Ancestors
• Generalized Selection and Ranking: Sorted Matrices
• Fast Algorithms for Diameter-Optimally Augmenting Paths
• Minimizing the Diameter of a Network Using Shortcut Edges
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Diameter increase caused by edge deletion
• Decreasing the diameter of bounded degree graphs
• Finding kth paths and p-centers by generating and searching good data structures
• Unnamed Item
• Unnamed Item