Packing and covering a tree by subtrees (Q1101129): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Uncapacitated lot-sizing: The convex hull of solutions / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4093489 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3328583 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Connected and alternating vectors: Polyhedra and algorithms / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Solving covering problems and the uncapacitated plant location problem on trees / rank | |||
Normal rank | |||
Revision as of 15:46, 18 June 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
