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)
Content information:
Item Type: Paper (Technical Report)
Citations: No citation data.
Uncontrolled Keywords: node cover NPC star
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C70 Factorization, matching, covering and packing

    		•
    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