论文标题
恒定直径增强问题的复杂性和算法
Complexity and algorithms for constant diameter augmentation problems
论文作者
论文摘要
我们研究以下问题：对于给定的整数$ d，k $和Graph $ g $，我们可以通过最多$ k $ edge Deletions获得直径$ d $的图表吗？我们确定了$ d $的不同值的计算复杂性和相关问题。
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$.
