Efficient algorithms for a simple network design problem

Abstract We consider the following simple network design problem. The input consists of n weighted nodes, and the output is an edge‐weighted connected network such that the total weight of the edges incident to a node is at least the given weight of the node. We aim to design the cheapest connected ... View More