On a famliy of stars of maximal weight covering exactly k nodes

Hagemeier, Christian and Hochstättler, Winfried (2004) On a famliy of stars of maximal weight covering exactly k nodes.
Technical Report , 3 p.

Abstract

We prove the NP--hardness of the following decision problem: given a complete graph with edge weights w_ein {mathbb Z}_+ , kin {mathbb Z}_+ , and w^starin {mathbb Z}_+ . Does there exist an edge induced subgraph with exactly k nodes and total weight at least w^star while each connected component is a star, i.e. a tree of depth 1.


Actions:
Download: [img] Postscript
Download (224Kb) | Preview
Download: [img] PDF
Download (72Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2004-467
Depositing User: Christian Hagemeier
Date Deposited: 25 Mar 2004 00:00
Last Modified: 12 Jan 2012 10:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/467