Packing of arborescences with matroid constraints via matroid intersection

DOI10.1007/S10107-019-01377-0MaRDI QIDQ2188242zbMATH OpenOpenAlexFDO

Authors Csaba Király, Zoltán Szigeti, Shin-Ichi Tanigawa

Publication date 10 June 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

Recommendations

• Reachability in arborescence packings
• On reachability mixed arborescence packing
• Matroid-Based Packing of Arborescences
• Old and new results on packing arborescences in directed hypergraphs
• On packing spanning arborescences with matroid constraint

Cites work

• A THEOREM ON INDEPENDENCE RELATIONS
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Arc-disjoint in-trees in directed graphs
• Blocking optimal k-arborescences
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Covering intersecting bi-set families under matroid constraints
• Exact and approximation algorithms for weighted matroid intersection
• scientific article; zbMATH DE number 3488914 (Why is no real title available?)
• scientific article; zbMATH DE number 3297114 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Matroid Intersection
• Matroid intersection algorithms
• Matroid-Based Packing of Arborescences
• Matroids and the greedy algorithm
• NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
• Old and new results on packing arborescences in directed hypergraphs
• On maximal independent arborescence packing
• On packing spanning arborescences with matroid constraint
• Packing arborescences
• Rooted \(k\)-connections in digraphs
• Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries
• Submodular functions and optimization.

Cited in

(13)

• 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
• Reachability in arborescence packings
• Packing of maximal independent mixed arborescences
• On reachability mixed arborescence packing
• Non-submodular maximization with matroid and knapsack constraints
• On packing spanning arborescences with matroid constraint
• Matroid-Based Packing of Arborescences
• Approximate cut \& packing ratios for multi-commodity arborescences
• Matroid-reachability-based decomposition into arborescences
• Regular packing of rooted hyperforests with root constraints in hypergraphs

This page was built for publication: Packing of arborescences with matroid constraints via matroid intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2188242)