The parametric complexity of graph diameter augmentation

DOI10.1016/j.dam.2013.01.016zbMath1287.05035OpenAlexW2148324291MaRDI QIDQ2446345

James Nastos, Donovan R. Hare, Yong Gao

Publication date: 16 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.01.016

zbMATH Keywords

reductiongraph augmentationfixed-parameter tractabilitygraph diameter\(W[2\)-hard]

Mathematics Subject Classification ID

Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

Algorithms for radius-optimally augmenting trees in a metric space ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths ⋮ Almost optimal algorithms for diameter-optimally augmenting trees ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ Augmenting graphs to minimize the radius ⋮ On the fixed-parameter tractability of the maximum connectivity improvement problem ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Finding diameter-reducing shortcuts in trees ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ 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 ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ 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 ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ 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
• New graph classes of bounded clique-width
• A tree representation for \(P_ 4\)-sparse graphs
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Diameter increase caused by edge deletion
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Dominating cliques in graphs

This page was built for publication: The parametric complexity of graph diameter augmentation