Augmenting graphs to minimize the diameter
From MaRDI portal
Publication:494792
DOI10.1007/978-3-642-45030-3_36zbMATH Open1319.68156arXiv1309.5172OpenAlexW2014732416MaRDI QIDQ494792FDOQ494792
Luke Mathieson, Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson
Publication date: 2 September 2015
Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)
Abstract: We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT 4-approximation algorithm for the problem.
Full work available at URL: https://arxiv.org/abs/1309.5172
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fibonacci heaps and their uses in improved network optimization algorithms
- Bounded-diameter minimum-cost graph 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
- Parametrized complexity theory.
- Diameter increase caused by edge deletion
- Design networks with bounded pairwise distance
- The parametric complexity of graph diameter augmentation
- Minimizing the Diameter of a Network Using Shortcut Edges
- Decreasing the diameter of cycles
- Decreasing the diameter of bounded degree graphs
- Augmenting graphs to minimize the diameter
- Improved approximability and non-approximability results for graph diameter decreasing problems
Cited In (27)
- An improved algorithm for diameter-optimally augmenting paths in a metric space
- Algorithms for radius-optimally augmenting trees in a metric space
- Algorithms for radius-optimally augmenting trees in a metric space
- Computing optimal shortcuts for networks
- Shortcut sets for the locus of plane Euclidean networks
- Augmenting outerplanar graphs to meet diameter requirements
- A linear-time algorithm for radius-optimally augmenting paths in a metric space
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- Finding diameter-reducing shortcuts in trees
- A survey of parameterized algorithms and the complexity of edge modification
- Fast Algorithms for Diameter-Optimally Augmenting Paths
- Minimizing the continuous diameter when augmenting a geometric tree with a shortcut
- Augmenting graphs to minimize the diameter
- A polynomial-time algorithm for outerplanar diameter improvement
- Title not available (Why is that?)
- Almost optimal algorithms for diameter-optimally augmenting trees
- Impact of the topology of urban streets on mobility optimization
- Title not available (Why is that?)
- Complexity and algorithms for constant diameter augmentation problems
- A Polynomial-Time Algorithm for Outerplanar Diameter Improvement
- Augmenting graphs to minimize the radius
- Shortcutting directed and undirected networks with a degree constraint
- A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space
- Shortcuts for the circle
- Title not available (Why is that?)
- Improving the Betweenness Centrality of a Node by Adding Links
- Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees
Recommendations
- Augmenting graphs to minimize the diameter 👍 👎
- Augmenting graphs to minimize the radius 👍 👎
- Title not available (Why is that?) 👍 👎
- The parametric complexity of graph diameter augmentation 👍 👎
- Augmenting outerplanar graphs to meet diameter requirements 👍 👎
- Approximation Algorithms for Graph Augmentation 👍 👎
- Approximation algorithms for graph augmentation 👍 👎
- On finding augmenting graphs 👍 👎
- On the minimum local-vertex-connectivity augmentation in graphs 👍 👎
- Title not available (Why is that?) 👍 👎
This page was built for publication: Augmenting graphs to minimize the diameter
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494792)
