The complexity of designing a network with minimum diameter

Unknown author(s)

Networks · 1981 · 57 citations · 7 references

Concepts

Abstract

Abstract Given a graph G with edge lengths and costs, we wish to find a subgraph F of G which connects up all the original vertices and minimizes the maximum distance in F , subject to a budget constraint on the sum of the edge costs. In this note we establish NP‐hardness for the design problem, even for the simple case where G is a planar graph with maximum degree 3 and the budget restricts the choice to spanning trees. Moreover, the problem of finding a near optimal subgraph F is also NP‐hard.

References

7