Packing and covering a tree by subtrees (Q1101129)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Packing and covering a tree by subtrees |
scientific article |
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
