Supermodularity in unweighted graph optimization. III: Highly connected digraphs

DOI10.1287/MOOR.2017.0883MaRDI QIDQ5219669zbMATH OpenOpenAlexFDO

Authors Kristóf Bérczi, András Frank

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.05729

zbMATH Keywords

\(k\)-connected digraphsconnectivity augmentationdegree-sequences

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: By generalizing a recent result of Hong, Liu, and Lai on characterizing the degree-sequences of simple strongly connected directed graphs, a characterization is provided for degree-sequences of simple $k$-node-connected digraphs. More generally, we solve the directed node-connectivity augmentation problem when the augmented digraph is degree-specified and simple. As for edge-connectivity augmentation, we solve the special case when the edge-connectivity is to be increased by one and the augmenting digraph must be simple.

Recommendations

• Superconnected circulant digraphs
• Hypergraph connectivity augmentation
• Sufficient conditions for digraphs to be maximally connected and super-connected
• Supermodularity in unweighted graph optimization. I: Branchings and matchings
• The superconnectivity of large digraphs and graphs

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A theorem on flows in networks
• An algorithm to increase the node-connectivity of a digraph by one
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Characterization of digraphic sequences with strongly connected realizations
• Combinatorial Matrix Theory
• Combinatorial Properties of Matrices of Zeros and Ones
• Connections in combinatorial optimization
• Existence of k-edge connected ordinary graphs with prescribed degrees
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
• Local Restrictions for Various Classes of Directed Graphs
• Matching theory
• Matrices of 0's and 1's with total support
• Minimal edge-coverings of pairs of sets
• On the existence of N‐connected graphs with prescribed degrees (n ≧ 2)
• Primal-dual approach for directed vertex connectivity augmentation and generalizations
• Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard: A solution to the 2-atom problem in discrete tomography
• Studies on directed graphs. I, II
• Supermodularity in unweighted graph optimization. I: Branchings and matchings
• Supermodularity in unweighted graph optimization. II: Matroidal term rank augmentation

Cited in

(6)

• Packing of maximal independent mixed arborescences
• Packing branchings under cardinality constraints on their root sets
• On the L  ∞ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs
• Technical Note—Preservation of Supermodularity in Parametric Optimization Problems with Nonlattice Structures
• Supermodularity in unweighted graph optimization. I: Branchings and matchings
• Supermodularity in unweighted graph optimization. II: Matroidal term rank augmentation

This page was built for publication: Supermodularity in unweighted graph optimization. III: Highly connected digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219669)