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: |
Download (229kB) | Preview |
---|---|
Download: |
Download (74kB) | Preview |
Editorial actions: | ![]() |
Content information:
Item Type: | Paper (Technical Report) |
---|---|
Citations: | No citation data. |
Uncontrolled Keywords: | node cover NPC star |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle |
Related URLs: |
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 |