<p>Minimum Diameter Spanning Subgraph is what you should be looking for. It is NP-Hard to compute even in the case of planar graphs. <a href="http://onlinelibrary.wiley.com/doi/10.1002/net.3230110110/abstract">This paper</a> gives a nice overview.</p>

CC BY-SA 3.0
2012-02-16T22:27:51.980Z
2012-02-16T22:43:37.460Z
2012-02-16T22:43:37.460Z
Nicholas Mancuso
<p>The idea of a diameter constrained MST is that you keep all vertices connected and within a certain distance of each other. But all papers I've seen keep the requirement that you produce a tree, when allowing cycles could help reduce the diameter. <strong>Does anyone know any papers that explore this?</strong> (It's difficult to search for.)</p>

<p>For example, consider a complete graph with vertices arranged in a circle on a plane (edge weight = Euclidean distance). The MST (e.g. via Prim's) will follow the circle, so that the <em>diameter of the graph</em> is roughly the <em>circumference of the circle</em>. By allowing the final edge to be connected we can halve the diameter, without increasing the total weight much.</p>

CC BY-SA 3.0
2012-02-16T22:29:52.557Z
It's not very clear what you're asking for. What are your constraints, and which is your objective function? My guess is that you want to constrain the number of edges, and minimize the diameter. Or vice versa?
zotachidil
CC BY-SA 3.0
2012-02-17T00:19:35.833Z
Well, it is understandable that all papers on diameter-constrained _MST_ keep the requirement of tree….
Tsuyoshi Ito
<cc.complexity-theory><reference-request><graph-theory>
Diameter Constrained Minimum Spanning Graph
Dijkstra
# Diameter Constrained Minimum Spanning Graph

(Asked by: username_0 on 2012-02-16)

The idea of a diameter constrained MST is that you keep all vertices connected and within a certain distance of each other. But all papers I've seen keep the requirement that you produce a tree, when allowing cycles could help reduce the diameter. **Does anyone know any papers that explore this?** (It's difficult to search for.)

For example, consider a complete graph with vertices arranged in a circle on a plane (edge weight = Euclidean distance). The MST (e.g. via Prim's) will follow the circle, so that the *diameter of the graph* is roughly the *circumference of the circle*. By allowing the final edge to be connected we can halve the diameter, without increasing the total weight much.

**Tags:** cc.complexity-theory, reference-request, graph-theory

> **Comments:**
> **username_1**: It's not very clear what you're asking for. What are your constraints, and which is your objective function? My guess is that you want to constrain the number of edges, and minimize the diameter. Or vice versa?  
> **username_2**: Well, it is understandable that all papers on diameter-constrained _MST_ keep the requirement of tree….  

---

## 1 answers

### Answer by username_3 on 2012-02-16. Score: 12 | Accepted answer

Minimum Diameter Spanning Subgraph is what you should be looking for. It is NP-Hard to compute even in the case of planar graphs. [This paper](http://onlinelibrary.wiley.com/doi/10.1002/net.3230110110/abstract) gives a nice overview.


---

