Fast Algorithms for Diameter-Optimally Augmenting Paths
From MaRDI portal
Publication:3448826
DOI10.1007/978-3-662-47672-7_55zbMath1440.68313OpenAlexW2293957677MaRDI QIDQ3448826
Joachim Gudmundsson, Christian Knauer, Ulrike Große, Fabian Stehn, Michiel H. M. Smid
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_55
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (14)
Minimizing the continuous diameter when augmenting a geometric tree with a shortcut ⋮ Geometric path problems with violations ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees ⋮ Algorithms for radius-optimally augmenting trees in a metric space ⋮ Shortcuts for the circle ⋮ Computing optimal shortcuts for networks ⋮ An improved algorithm for diameter-optimally augmenting paths 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 ⋮ Unnamed Item ⋮ Shortcut sets for the locus of plane Euclidean networks ⋮ 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
- Computing the dilation of edge-augmented graphs in metric spaces
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- How to decrease the diameter of triangle-free graphs
- Augmenting trees to meet biconnectivity and diameter constraints
- The parametric complexity of graph diameter augmentation
- Bounded-diameter minimum-cost graph problems
- Design networks with bounded pairwise distance
- Augmenting Outerplanar Graphs to Meet Diameter Requirements
- Augmenting the Connectivity of Planar and Geometric Graphs
- Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces
- Improving the Stretch Factor of a Geometric Network by Edge Augmentation
- Diameter increase caused by edge deletion
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- Decreasing the diameter of bounded degree graphs
- Diameter bounds for altered graphs
This page was built for publication: Fast Algorithms for Diameter-Optimally Augmenting Paths
