Supermodularity in Unweighted Graph Optimization III: Highly Connected Digraphs

References

• Beineke LW, Harary F (1965) Local restrictions for various classes of directed graphs. J. London Math. Soc. 40(1):87–95.Crossref, Google Scholar
• 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 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 (2017) 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. Combin. Theory, Ser. A 28(3):249–256.Crossref, Google Scholar
• Brualdi RA, Ryser HJ (1991) Combinatorial Matrix Theory (Cambridge University Press, Cambridge, UK).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 (1964) Existence of k-edge-connected ordinary graphs with prescribed degrees. J. Res. National Bureau Standards B68(2):73–74.Crossref, Google Scholar
• Ford LR, Fulkerson DR (1962) Flows in Networks (Princeton University Press, Princeton NJ).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 (2011) Connections in Combinatorial Optimization, Oxford Lecture Series in Mathematics and Its Applications (Oxford University Press, Oxford, UK), 38.Google Scholar
• Frank A, Jordán T (1995) Minimal edge-coverings of pairs of sets. J. Combin. Theory, Ser. B 65(1):73–110.Crossref, Google Scholar
• Frank A, Végh LA (2008) An algorithm to increase the node-connectivity of a digraph by one. Discrete Optim. 5(4):677–684.Crossref, Google Scholar
• Gale D (1957) A theorem on flows in networks. Pacific J. Math. 7(2):1073–1082.Crossref, 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
• Lovász L, Plummer M (1986) Matching Theory. Reprinted with Corrections: American Mathematical Society (Chelsea Publishing, North-Holland, Amsterdam), 2009.Google Scholar
• Mader W (1982) Konstruktion aller n-fach kantenzusammenhängenden Digraphen. Eur. J. Combinatorics 3(1):63–67.Crossref, Google Scholar
• Ore O (1956) Studies on directed graphs, I. Ann. Math. 63(3):383–406.Crossref, Google Scholar
• Ryser HJ (1957) Combinatorial properties of matrices of zeros and ones. Canadian J. Math. 9:371–377.Crossref, Google Scholar
• Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory, Ser. B 80(2):346–355.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
• Wang DL, Kleitman DJ (1972) On the existence of n-connected graphs with prescribed degrees (n ≥ 2). Networks 3(3):225–239.Crossref, Google Scholar