Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation

DOI10.1287/moor.2017.0902zbMath1434.05121arXiv1608.05730OpenAlexW2963506166MaRDI QIDQ5219668

András Frank, Kristóf Bérczi

Publication date: 12 March 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

augmentationmatroidsbipartite matchingterm rank

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items (5)

Fair integral submodular flows ⋮ Packing of maximal independent mixed arborescences ⋮ Packing branchings under cardinality constraints on their root sets ⋮ Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings ⋮ Supermodularity in Unweighted Graph Optimization III: Highly Connected Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Studies on directed graphs. I, II
• A theorem on flows in networks
• On complexity of special maximum matchings constructing
• Minimal edge-coverings of pairs of sets
• Partitioning to three matchings of given size is NP-complete for bipartite graphs
• Complexity of a disjoint matching problem on bipartite graphs
• Combinatorial Properties of Matrices of Zeros and Ones
• The Term Rank of a Matrix
• Primal-dual approach for directed vertex connectivity augmentation and generalizations
• Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings
• Admissible Mappings between Dependence Spaces

This page was built for publication: Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation