Threshold-based preprocessing for approximating the weighted dense k-subgraph problem

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 and difficult to approximate if the underlying graph does not satisfy the triangle inequality.

MoreLess

Year of publication:	2014
Authors:	Borgwardt, S. ; Schmiedl, F.
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 234.2014, 3, p. 631-640
Publisher:	Elsevier
Subject:	(I) Graph theory \| OR in forestry \| Dense subgraph \| Approximation algorithms

Online Resource

Check full text access |

More access options

Check Google Scholar

In libraries world-wide (WorldCat)

In German libraries (KVK)

subito order

I need help

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10011052704