Packing and covering a tree by subtrees (Q1101129): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 02:11, 5 March 2024
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
