E-resources
PDF-
Kim, Eun Jung; Milanič, Martin; Monnot, Jérôme; Picouleau, Christophe
Theoretical computer science, 02/2022, Volume: 904Journal Article
•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.•For d=3, the problem is related to Moore graphs and solvable in polynomial time.•For all d>4, the problem is NP-complete.•The NP-completeness results are proved for various values of the diameter of the input graph. 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.
