Matroid-Based Packing of Arborescences

DOI10.1137/120883761zbMATH Open1268.05165OpenAlexW2062251071MaRDI QIDQ5300512FDOQ5300512

Authors Olivier Durand de Gevigney, Viet Hang Nguyen, Zoltán Szigeti

Publication date 27 June 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.1985

zbMATH Keywords

matroidpackingarborescence

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Combinatorial aspects of matroids and geometric lattices (05B35) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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

(19)

• Complexity of packing common bases in matroids
• Packing circuits in matroids
• scientific article; zbMATH DE number 7378329 (Why is no real title available?)
• Matroid-rooted packing of arborescences
• A note on disjoint arborescences
• Packing of maximal independent mixed arborescences
• Polymatroid-based capacitated packing of branchings
• Packing of spanning mixed arborescences
• Two packing problems on \(k\)-matroid trees
• Packing of arborescences with matroid constraints via matroid intersection
• On maximal independent arborescence packing
• On packing spanning arborescences with matroid constraint
• Old and new results on packing arborescences in directed hypergraphs
• On packing spanning arborescences with matroid constraint
• A matroid approach to finding edge connectivity and packing arborescences
• The \(b\)-branching problem in digraphs
• Covering intersecting bi-set families under matroid constraints
• Packing branchings under cardinality constraints on their root sets
• Reachability in arborescence packings

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)