Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings

References

• Bérczi K, Frank A (2018) Supermodularity in unweighted graph optimization II: Matroidal term rank augmentation. Math. Oper. Res., ePub ahead of print February 2, 2018, https://doi.org/10.1287/moor.2017.0902.Google Scholar
• Bérczi K, Frank A (2018) Supermodularity in unweighted graph optimization III: Highly-connected digraphs. Math. Oper. Res., ePub ahead of print February 2, 2018, https://doi.org/10.1287/moor.2017.0883.Google Scholar
• Bérczi K, Frank A (2018) Supermodularity in Unweighted Graph Optimization IV: Algorithms. In preparation.Google Scholar
• Brualdi RA (1980) Matrices of 0’s and 1’s with total support. J. Combinatorial Theory Ser. A 28(3):249–256.Crossref, Google Scholar
• Brualdi RA, Ross JA (1980) On Ryser’s maximum term rank formula. Linear Algebra Appl. 29:33–38.Crossref, Google Scholar
• Cai M-C (1983) Arc-disjoint arborescences of digraphs. J. Graph Theory 7(2):235–240.Crossref, Google Scholar
• Dürr C, Guinez F, Matamala M (2012) Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard. SIAM J. Discrete Math. 26(1):330–352.Crossref, Google Scholar
• Edmonds J (1973) Edge-disjoint branchings. Rustin B, ed. Combinatorial Algorithms (Acad. Press, New York), 91–96.Google Scholar
• Edmonds J, Giles R (1977) A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1:185–204.Crossref, Google Scholar
• Eswaran KP, Tarjan RE (1976) Augmentation problems. SIAM J. Comput. 5(4):653–665.Crossref, Google Scholar
• Folkman J, Fulkerson DR (1969) Edge-colorings in bipartite graphs. Bose RC, Dowling TA, eds. Proc. Combinatorial Math. Its Applications Conf. (University of North Carolina, Chapel Hill), 561–577.Google Scholar
• Ford LR, Fulkerson DR (1962) Flows in Networks (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Frank A (1978) On disjoint trees and arborescences. Algebraic Methods in Graph Theory, Colloquia Mathematica Soc. J. Bolyai, Vol. 25 (North-Holland, Amsterdam), 159–169.Google Scholar
• Frank A (1984) Generalized polymatroids. Finite and Infinite Sets, Colloquia Mathematica Soc. J. Bolyai, Vol. 37 (North-Holland, Amsterdam), 285–294.Crossref, Google Scholar
• Frank A (1981) How to make a digraph strongly connected. Combinatorica 1(2):145–153.Crossref, Google Scholar
• Frank A (2003) Restricted t-matchings in bipartite graphs. Discrete Appl. Math. 131(2):337–346.Crossref, Google Scholar
• Frank A (1992) Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5(1):22–53.Crossref, Google Scholar
• Frank A (1994) Connectivity augmentation problems in network design. Birge JR, Murty KG, eds. Mathematical Programming: State of the Art (The University of Michigan, Ann Arbor), 34–63.Google Scholar
• Frank A (2011) Connections in Combinatorial Optimization, Oxford Lecture Series in Mathematics and Its Applications, Vol. 38 (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
• Frank A, Tardos É (1988) Generalized polymatroids and submodular flows. Math. Programming, Ser. B 42(1–3):489–563.Crossref, Google Scholar
• Frank A, Tardos É (1989) An application of submodular flows. Linear Algebra and Its Appl. 114–115:329–348.Crossref, Google Scholar
• Gale D (1957) A theorem on flows in networks. Pacific J. Math. 7(2):1073–1082.Crossref, Google Scholar
• Győri E (1985) Covering simply connected regions by rectangles. Combinatorica 5(1):53–55.Crossref, Google Scholar
• Haber RM (1960) Term rank of 0, 1 matrices. Rendiconti del Seminario Matematico della Universita di Padova, Tome 30:24–51.Google Scholar
• Hong Y, Liu Q, Lai H-J (2017) Characterization of digraphic sequences with strongly connected realizations. J. Graph Theory 84(2):191–201.Crossref, Google Scholar
• Kamalian RR, Mkrtchyan VV (2008) On complexity of special maximum matchings constructing. Discrete Math. 308(10):1792–1800.Crossref, Google Scholar
• Kamiyama N (2014) Arborescence problems: Theorems and algorithms. Interdisciplinary Inform. Sci. 20(1):51–70.Crossref, Google Scholar
• Király T (2016) Interview with the authors. July. Eötvös Loránd University, Budapest.Google Scholar
• Lovász L (1970) A generalization of Kőnig’s theorem. Acta. Math. Acad. Sci. Hungar. 21(3–4):443–446.Crossref, Google Scholar
• Lovász L (1976) On two minimax theorems in graph theory. J. Combinatorial Theory, Ser. B 21(2):96–103.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. Inform. 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
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24 (Springer, Berlin).Google Scholar
• Soto JA, Telha C (2014) Independent sets and bicolored rectangular families. Preprint arXiv:1411.2311.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