ComputingComputer ScienceDesignAlgorithmsComputer NetworksOptimizationCombinatorial OptimizationGraph AlgorithmsGraph TheoryNetwork DesignNetwork DiameterNetwork OptimizationBudget Constraint OptimizationComputational Complexity Of Graph AlgorithmsLower Bounds On DiameterNetwork Design ProblemsPlanar Graph Algorithms
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.
7
Some simplified NP-complete graph problems
M. R. Garey, David S. Johnson, Larry Stockmeyer · Theoretical Computer Science · 1976 · 2.1K citations
P-Complete Approximation Problems
Sartaj Sahni, Teofilo F. Gonzalez · Journal of the ACM · 1976 · 1.7K citations · Full text
On the Computational Complexity of Combinatorial Problems
Richard M. Karp · Networks · 1975 · 712 citations
Finding Minimum Spanning Trees
David R. Cheriton, Robert E. Tarjan · SIAM Journal on Computing · 1976 · 429 citations