Packing and covering a tree by subtrees (Q1101129)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Publication:1101129 |
scientific article; zbMATH DE number 4045791
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Packing and covering a tree by subtrees |
scientific article; zbMATH DE number 4045791 |
Statements
Packing and covering a tree by subtrees (English)
0 references
1986
0 references
The authors consider various generalization for the problem of packing subtrees into a tree, and describe the structure of the vertices for the polyhedra associated with these problems. They also give efficient algorithms for optimization over the polyhedra, and prove that the related problem of covering a tree by subtrees is polynomial-time solvable when the family of subtrees is ``fork-free'', using a reduction to a packing problem.
0 references
intersection graph
0 references
tree-matrix
0 references
greedy algorithm
0 references
0-1 programming
0 references
packing subtrees into a tree
0 references
polyhedra
0 references
algorithms
0 references
covering a tree by subtrees
0 references
0.863562285900116
0 references
0.863562285900116
0 references
0.8070360422134399
0 references
