Premium
The complexity of designing a network with minimum diameter
Author(s) -
Plesnik J.
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110110
Subject(s) - combinatorics , mathematics , graph , enhanced data rates for gsm evolution , constraint (computer aided design) , simple graph , planar graph , simple (philosophy) , mathematical optimization , computer science , discrete mathematics , artificial intelligence , geometry , philosophy , epistemology
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.