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$
  • 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 Feb 16 '12 at 22:29
  • 3
    $\begingroup$ Well, it is understandable that all papers on diameter-constrained MST keep the requirement of tree…. $\endgroup$ – Tsuyoshi Ito Feb 17 '12 at 0:19
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, privacy policy and cookie policy

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