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: |
Download (248kB) | Preview |
---|---|
Download: |
Download (89kB) | Preview |
Editorial actions: | ![]() |
Content information:
Item Type: | Paper (Technical Report) |
---|---|
Citations: | 2 (Google Scholar) | |
Uncontrolled Keywords: | node cover trees polynomial-time algorithm |
Subjects: |
|
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 |