On decorating Christmas trees

Hagemeier, Christian and Fuchs, Bernhard and Räbiger, Dirk and Peis, Britta (2004) On decorating Christmas trees.
Technical Report , 6 p.

Abstract

The following decision problem is regarded in this note: given a tree, decide if it is possible to cover exactly k nodes of the tree with stars (that is with trees of depth 1. We give a proof of the polynomiality of the problem which directly leads to a linear time algorithm.


Actions:
Download: [img] Postscript
Download (248kB) | Preview
Download: [img] PDF
Download (89kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: 2 (Google Scholar) |
Uncontrolled Keywords: node cover trees polynomial-time algorithm
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-468
      Depositing User: Christian Hagemeier
      Date Deposited: 20 Jan 2006 00:00
      Last Modified: 12 Jan 2012 10:43
      URI: http://e-archive.informatik.uni-koeln.de/id/eprint/468