Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation

References

• Bérczi K, Frank A (2018) Supermodularity in unweighted graph optimization I: Branchings and matchings. Math. Oper. Res., ePub ahead of print February 2, 2018, https://doi.org/10.1287/moor.2017.0881.Google Scholar
• Bérczi K, Frank A (2018) Supermodularity in unweighted graph optimization IV: Algorithms. In preparation.Google Scholar
• Brualdi RA (1970) Admissible mappings between dependence spaces. Proc. London Math. Soc. 3(2):296–312.Crossref, Google Scholar
• Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. Guy R, Hanani H, Sauer N, Schönheim J, eds. Combinatorial Structures and Their Applications (Gordon and Breach, New York), 69–87.Google Scholar
• Frank A (2011) Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and Its Applications (Oxford University Press, Oxford, UK).Google Scholar
• Frank A, Jordán T (1995) Minimal edge-coverings of pairs of sets. J. Combinatorial Theory, Ser. B 65(1):73–110.Crossref, Google Scholar
• Gale D (1957) A theorem on flows in networks. Pacific J. Math. 7(2):1073–1082.Crossref, Google Scholar
• Kamalian RR, Mkrtchyan VV (2008) On complexity of special maximum matchings constructing. Discrete Math. 308(10):1792–1800.Crossref, Google Scholar
• Ore O (1956) Studies on directed graphs, I. Ann. Math. 63(3):383–406.Crossref, Google Scholar
• Pálvölgyi D (2014) Partitioning to three matchings of given size is NP-complete for bipartite graphs. Acta Universitatis Sapientiae, Informatica 6(2):206–209.Crossref, Google Scholar
• Puleo GJ (2016) Complexity of a disjoint matching problem on bipartite graphs. Information Processing Lett. 116(10):649–652.Crossref, Google Scholar
• Ryser HJ (1957) Combinatorial properties of matrices of zeros and ones. Canadian J. Math. 9:371–377.Crossref, Google Scholar
• Ryser HJ (1958) The term rank of a matrix. Canadian J. Math. 10:57–65.Crossref, Google Scholar
• Végh LA, Benczúr AA (2008) Primal-dual approach for directed vertex connectivity augmentation and generalizations. ACM Trans. Algorithms 4(2):1–21.Crossref, Google Scholar