Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation

• 成果类型: Article
• 署名作者: Berczi, Kristof; Frank, Andras
• 署名单位: Eotvos Lorand University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0902
• 发表日期: 2018
• 页码: 754-762
• 关键词: Complexity

摘要

Ryser's max term rank formula with graph theoretic terminology is equivalent to a characterization of degree sequences of simple bipartite graphs with a specific matching number. In a previous paper by the authors, a generalization was developed for the case when the degrees are constrained by upper and lower bounds. Here, two other extensions of Ryser's theorem are discussed. The first one is a matroidal model, while the second one settles the augmentation version. In fact, the two directions shall be integrated into one single framework.