Packing of arborescences with matroid constraints via matroid intersection

DOI10.1007/s10107-019-01377-0zbMath1441.05185OpenAlexW2931146240MaRDI QIDQ2188242

Zoltán Szigeti, Shin-ichi Tanigawa, Csaba Király

Publication date: 10 June 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-019-01377-0

Mathematics Subject Classification ID

Trees (05C05) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22)

Related Items

Reachability in arborescence packings, On reachability mixed arborescence packing, Packing of maximal independent mixed arborescences, Non-Submodular Maximization with Matroid and Knapsack Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arc-disjoint in-trees in directed graphs
• Rooted \(k\)-connections in digraphs
• On packing spanning arborescences with matroid constraint
• Old and new results on packing arborescences in directed hypergraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Submodular functions and optimization.
• Covering Intersecting Bi-set Families under Matroid Constraints
• On Maximal Independent Arborescence Packing
• NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
• Matroid Intersection
• Matroid intersection algorithms
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Exact and Approximation Algorithms for Weighted Matroid Intersection
• Blocking Optimal k-Arborescences
• Rooted-Tree Decompositions with Matroid Constraints and the Infinitesimal Rigidity of Frameworks with Boundaries
• Matroid-Based Packing of Arborescences
• Matroids and the greedy algorithm
• A THEOREM ON INDEPENDENCE RELATIONS