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.


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.

Download: [img] Postscript
Download (248kB) | Preview
Download: [img] PDF
Download (89kB) | Preview
Editorial actions: View Item View Item (Login required)
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