Proposed by Deepak Mehta, Cemalettin Ozturk, Luis Quesada, Barry O'Sullivan

Overview

Given an undirected graph with a set of nodes and a set of links, the Diameter and Degree Bounded Network Design Problem (DDBNDP) is to select a subset of links such that there exists a path between each pair of nodes whose length is bounded by a given constant, and the degree of each node must be greater than a given constant. The objective is to minimise the sum of the selected links.