Packing and covering a tree by subtrees
DOI10.1007/BF02579383zbMATH Open0642.05042OpenAlexW1977577374MaRDI QIDQ1101129FDOQ1101129
Authors: B. George 
Publication date: 1986
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579383
Recommendations
algorithmsgreedy algorithmpolyhedraintersection graph0-1 programmingcovering a tree by subtreespacking subtrees into a treetree-matrix
Trees (05C05) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of packing and covering (05B40)
Cites Work
- Title not available (Why is that?)
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Title not available (Why is that?)
- Solving covering problems and the uncapacitated plant location problem on trees
- Uncapacitated lot-sizing: The convex hull of solutions
- Connected and alternating vectors: Polyhedra and algorithms
Cited In (30)
- Title not available (Why is that?)
- Optimization problems in multiple subtree graphs
- On a labeling problem in graphs
- Models for planning capacity expansion in local access telecommunication networks
- The game of cops and eternal robbers
- A tree-covering problem arising in integrity of tree-structured data
- Covering a tree with rooted subtrees -- parameterized and approximation algorithms
- A dynamic programming algorithm for the local access telecommunication network expansion problem
- LS-LIB: a library of tools for solving production planning problems
- Title not available (Why is that?)
- Polyhedral properties of the \(K\)-median problem on a tree
- Optimizing constrained subtrees of trees
- Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
- Relaxations for two-level multi-item lot-sizing problems
- On star-cover and path-cover of a tree
- Covering, Packing and Generalized Perfection
- Kernelization and parameterized algorithms for covering a tree by a set of stars or paths
- Approximation Algorithms for k-Hurdle Problems
- Modelling piecewise linear concave costs in a tree partitioning problem
- Packing and covering with balls on Busemann surfaces
- Approximation algorithms for \(k\)-hurdle problems
- Finding minimum cost directed trees with demands and capacities
- Recognizing single-peaked preferences on a tree
- Lot-sizing with fixed charges on stocks: the convex hull
- Lot-size models with backlogging: Strong reformulations and cutting planes
- A minimum-length covering subtree of a tree
- Capacitated location-allocation problems on a line
- Covering a tree by a forest
- A path-decomposition theorem with applications to pricing and covering on trees
- Gain-sharing in urban consolidation centers
This page was built for publication: Packing and covering a tree by subtrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101129)
