Augmenting graphs to minimize the diameter

DOI10.1007/s00453-014-9886-4zbMath1319.68156arXiv1309.5172OpenAlexW2014732416MaRDI QIDQ494792

Luke Mathieson, Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson

Publication date: 2 September 2015

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsapproximation algorithmsparametrized complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (25)

Algorithms for radius-optimally augmenting trees in a metric space ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths ⋮ Impact of the topology of urban streets on mobility optimization ⋮ Improving the Betweenness Centrality of a Node by Adding Links ⋮ A Polynomial-Time Algorithm for Outerplanar Diameter Improvement ⋮ Almost optimal algorithms for diameter-optimally augmenting trees ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ Augmenting graphs to minimize the radius ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ 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 ⋮ Augmenting graphs to minimize the diameter ⋮ Shortcuts for the circle ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ 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 ⋮ Unnamed Item ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Augmenting trees to meet biconnectivity and diameter constraints
• The parametric complexity of graph diameter augmentation
• Bounded-diameter minimum-cost graph problems
• Parametrized complexity theory.
• Design networks with bounded pairwise distance
• Minimizing the Diameter of a Network Using Shortcut Edges
• Diameter increase caused by edge deletion
• Decreasing the diameter of cycles
• Decreasing the diameter of bounded degree graphs
• Fibonacci heaps and their uses in improved network optimization algorithms

This page was built for publication: Augmenting graphs to minimize the diameter