Matroid-Based Packing of Arborescences

DOI10.1137/120883761zbMATH Open1268.05165arXiv1207.1985OpenAlexW2062251071MaRDI QIDQ5300512FDOQ5300512

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

Publication date: 27 June 2013

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

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.

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

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

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)

Cited In (17)

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

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)