Abstract: We provide the directed counterpart of a slight extension of Katoh and Tanigawa's result on rooted-tree decompositions with matroid constraints. Our result characterises digraphs having a packing of arborescences with matroid constraints. It is a proper extension of Edmonds' result on packing of spanning arborescences and implies - using a general orientation result of Frank - the above result of Katoh and Tanigawa. We also give a complete description of the convex hull of the incidence vectors of the basic packings of arborescences and prove that the mimimum cost version of the problem can be solved in polynomial time.
Recommendations
- Packing of arborescences with matroid constraints via matroid intersection
- On packing spanning arborescences with matroid constraint
- On packing spanning arborescences with matroid constraint
- A matroid approach to finding edge connectivity and packing arborescences
- Packing of maximal independent mixed arborescences
- scientific article; zbMATH DE number 270249
- Packing arborescences
- On maximal independent arborescence packing
- Packing of spanning mixed arborescences
- Two packing problems on \(k\)-matroid trees
Cited in
(26)- Packing circuits in matroids
- Two packing problems on \(k\)-matroid trees
- On packing spanning arborescences with matroid constraint
- Old and new results on packing arborescences in directed hypergraphs
- A matroid approach to finding edge connectivity and packing arborescences
- Complexity of packing common bases in matroids
- Reachability in arborescence packings
- Packing of arborescences with matroid constraints via matroid intersection
- The \(b\)-branching problem in digraphs
- Packing of maximal independent mixed arborescences
- Packing branchings under cardinality constraints on their root sets
- Polymatroid-based capacitated packing of branchings
- Covering intersecting bi-set families under matroid constraints
- On maximal independent arborescence packing
- scientific article; zbMATH DE number 7378329 (Why is no real title available?)
- On packing spanning arborescences with matroid constraint
- A note on disjoint arborescences
- Packing of spanning mixed arborescences
- Matroid-rooted packing of arborescences
- Covering a supermodular-like function in a mixed hypergraph
- Approximate cut \& packing ratios for multi-commodity arborescences
- Matroid-reachability-based decomposition into arborescences
- Regular packing of rooted hyperforests with root constraints in hypergraphs
- Reconfiguration of the union of arborescences
- Reconfiguration of the union of arborescences
- Packing mixed hyperarborescences
This page was built for publication: Matroid-Based Packing of Arborescences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300512)
