Borgwardt, S.; Schmiedl, F. - In: European Journal of Operational Research 234 (2014) 3, pp. 631-640
Based on an application in forestry, we study the dense k-subgraph problem: Given a parameter k∈N and an undirected weighted graph G, the task is to find a subgraph of G with k vertices such that the sum of the weights of the induced edges is maximized. The problem is well-known to be NP-hard...