8
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – zotachidil
    Commented Feb 16, 2012 at 22:29
  • 3
    $\begingroup$ Well, it is understandable that all papers on diameter-constrained MST keep the requirement of tree…. $\endgroup$ Commented Feb 17, 2012 at 0:19

1 Answer 1

12
$\begingroup$

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 gives a nice overview.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.