Complexity and algorithms for constant diameter augmentation problems

2020/10/01 by Kim, Eun Jung, Martin Milanič, Milanic, Martin +4
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2010.00273

openalex publication_date 2020/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the following problem: for given integers d,k and graph G, can we obtain a graph with diameter d via at most k edge deletions ? We determine the computational complexity of this and related problems for different values of d.

Related

• A note on the hardness of graph diameter augmentation problems
• A Polynomial-time Algorithm for Outerplanar Diameter Improvement
• Augmenting graphs to minimize the diameter
• Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees
• Obstructions to faster diameter computation: Asteroidal sets