<p>Given edge weighted undirected graph the problem asks to output a spanning tree $T$ of minimum weight such that the path between any two vertices in the tree $T$ is bounded by the input $k$. One of the related paper is at <a href="http://www.sciencedirect.com/science/article/pii/S0166218X99001110">http://www.sciencedirect.com/science/article/pii/S0166218X99001110</a> .</p>

<p>However i could not find other relevant results which improvised over it in general case. Can anyone please refer me the state of the art in this problem. I am also looking for results on unweighted undirected graphs which i couldn't get. I tried to google out and follow the citations but couldn't get what i wanted.</p>

CC BY-SA 3.0
2011-07-05T19:24:19.950Z
my interest is in both the upper bound as well as the lower bound.
user5153
CC BY-SA 3.0
2011-07-05T19:46:09.493Z
also i am specifically more interested in algorithms which return tree of optimum cost and violate only the diameter constraint.
user5153
CC BY-SA 3.0
2011-07-06T12:20:32.833Z
The problem is NP-complete if the diameter bound is greater than 3 and even if edge weights are restricted to {1, 2}. It is solvable in polynomial time when all edge weights are identical or when the bound is less than or equal 3.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-07-06T18:54:23.393Z
@Mohammad Al-Turkistany yes i realized the problem on graphs having equal weight is in P. Thanks for that. However im looking for more results as described above in question and comments.
user5153
CC BY-SA 3.0
2011-07-07T01:17:35.780Z
Does this paper have any ideas that might be of use: http://www.math.tau.ac.il/~hassin/diameter_95.pdf
Joseph Malkevitch
<reference-request><approximation-algorithms><approximation-hardness>
Results regarding Bounded Diameter Minimum Spanning Tree
user5153
# Results regarding Bounded Diameter Minimum Spanning Tree

(Asked by: username_0 on 2011-07-05)

Given edge weighted undirected graph the problem asks to output a spanning tree $T$ of minimum weight such that the path between any two vertices in the tree $T$ is bounded by the input $k$. One of the related paper is at <http://www.sciencedirect.com/science/article/pii/S0166218X99001110> .

However i could not find other relevant results which improvised over it in general case. Can anyone please refer me the state of the art in this problem. I am also looking for results on unweighted undirected graphs which i couldn't get. I tried to google out and follow the citations but couldn't get what i wanted.

**Tags:** reference-request, approximation-algorithms, approximation-hardness
> **Comments:**
> **username_0**: my interest is in both the upper bound as well as the lower bound.  
> **username_0**: also i am specifically more interested in algorithms which return tree of optimum cost and violate only the diameter constraint.  
> **username_1**: The problem is NP-complete if the diameter bound is greater than 3 and even if edge weights are restricted to {1, 2}. It is solvable in polynomial time when all edge weights are identical or when the bound is less than or equal 3.  
> **username_0**: @Mohammad Al-Turkistany yes i realized the problem on graphs having equal weight is in P. Thanks for that. However im looking for more results as described above in question and comments.  
> **username_2**: Does this paper have any ideas that might be of use: http://www.math.tau.ac.il/~hassin/diameter_95.pdf  

---

## 0 answers

