Augmenting Graphs to Meet Edge-Connectivity Requirements
What is the minimum number of edges to be added to a given graph \(G\) so that in the resulting graph the edge-connectivity between every pair \(\{u,v\}\) of its nodes is at least a prescribed value \(r(u,v)\)? In this splendid paper, the author finds a min-max formula for this number and describes a polynomial time algorithm to compute it. The directed counterpart is shown to be NP-complete in general but is solved in the case \(r(u,v)\equiv k\geq 1\). The proof uses splitting theorems of \textit{W. Mader} [Ann. Discrete Math. 3, 145-164 (1978; Zbl 0389.05042)] and Lovász, which are given new proofs. It also uses techniques concerning submodular functions and polymatroids. However, the author has generously converted the proofs so as to avoid this theory, and supplies details of the relationship in separate sections.
- Augmenting edge and vertex connectivities simultaneously
- Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
- Connectivity augmentation of graphs
- Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
- \(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs.
- Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs
- Inapproximability of survivable networks
- Vertex fusion under distance constraints
- On a theorem of Mader
- Triangulating planar graphs while minimizing the maximum degree
- Structures of subpartitions related to a submodular function minimization
- Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
- On the minimum local-vertex-connectivity augmentation in graphs
- Edge splitting and connectivity augmentation in directed hypergraphs.
- Splitting off edges between two subsets preserving the edge-connectivity of the graph.
- Increasing digraph arc-connectivity by arc addition, reversal and complement
- Path-contractions, edge deletions and connectivity preservation
- Independence free graphs and vertex connectivity augmentation
- Connectivity interdiction
- On the minor-minimal 2-connected graphs having a fixed minor
- Polyhedral structure of submodular and posi-modular systems
- Minimal edge-coverings of pairs of sets
- Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks
- The \((2, k)\)-connectivity augmentation problem: algorithmic aspects
- Decreasing minimization on M-convex sets: algorithms and applications
- Relaxed and approximate graph realizations
- Shorter tours and longer detours: uniform covers and a bit beyond
- On the cycle augmentation problem: hardness and approximation algorithms
- Vertex-weighted realizations of graphs
- Making bidirected graphs strongly connected
- Augmenting weighted graphs to establish directed point-to-point connectivity
- Covering symmetric supermodular functions with graph edges: a short proof of a theorem of Benczúr and Frank
- Degree sequence for \(k\)-arc strongly connected multiple digraphs
- Approximating node-connectivity augmentation problems
- A unifying approach to splitting-off
- Covering symmetric semi-monotone functions
- Edge-splittings preserving local edge-connectivity of graphs
- Multigraph augmentation under biconnectivity and general edge-connectivity requirements
- A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
- Approximating source location and star survivable network problems
- Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph
- A note on minimizing submodular functions
- The generalized terminal backup problem
- Characterization of digraphic sequences with strongly connected realizations
- Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph
- A Survey on Covering Supermodular Functions
- Edge-connectivity augmentations of~graphs~and~hypergraphs
- A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation
- On integer network synthesis problem with tree-metric cost
- Extension to Even Triangulations
- A New Approach to Splitting-Off
- Minimum augmentation of a tree to a K-edge-connected graph
- Characterizing and recognizing generalized polymatroids
- Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time
- scientific article; zbMATH DE number 1303570 (Why is no real title available?)
- Edge-Connectivity Augmentation with Partition Constraints
- Extremal graphs in connectivity augmentation
- Augmenting edge and vertex connectivities simultaneously
- Graph orientations with set connectivity requirements
- Structured connectivity augmentation
- Approximating Minimum Cost Connectivity Orientation and Augmentation
- Testing \(k\)-edge-connectivity of digraphs
- Augmenting edge-connectivity between vertex subsets
- Highly edge-connected detachments of graphs and digraphs
- Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph
- A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem
- How to make a strongly connected digraph two-connected
- Structured connectivity augmentation
- Path-contractions, edge deletions and connectivity preservation
- Efficiently realizing interval sequences
- Strongly connectable digraphs and non-transitive dice
- Supermodularity in unweighted graph optimization. I: Branchings and matchings
- Supermodularity in unweighted graph optimization. III: Highly connected digraphs
- Robustness and strong attack tolerance of low-diameter networks
- Composed degree-distance realizations of graphs
- Posimodular function optimization
- Fast exact algorithms for survivable network design with uniform requirements
- A new contraction technique with applications to congruency-constrained cuts
- Realization problems on reachability sequences
- Composed degree-distance realizations of graphs
- Bipartition constrained edge-splitting in directed graphs
- Augmenting trees so that every three vertices lie on a cycle
- Complexity of (arc)-connectivity problems involving arc-reversals or deorientations
- A polyhedral approach to planar augmentation and related problems
- Fault-tolerant graph realizations in the congested clique
- A survey of parameterized algorithms and the complexity of edge modification
- Optimal bi-level augmentation for selective! enhancing graph connectivity with applications
- Augmenting the edge connectivity of planar straight line graphs to three
- Testing Eulerianity and connectivity in directed sparse graphs
- Splitting off operation for binary matroids and its applications
- Connectivity augmentation in planar straight line graphs
- Edge-connectivity augmentation of simple graphs
- Splitting-off in hypergraphs
- Submodular functions in graph theory
- Splitting-off in hypergraphs
- On arborescence packing augmentation in hypergraphs
- Temporal graph realization from fastest paths
- Graph connectivity and its augmentation: Applications of MA orderings
- Augmenting plane straight-line graphs to meet parity constraints
- Hypergraph connectivity augmentation in strongly polynomial time
- Realizing temporal transportation trees
- Bicriteria approximation for k-edge-connectivity
- Network design with edge-connectivity and degree constraints
- Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
- Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
This page was built for publication: Augmenting Graphs to Meet Edge-Connectivity Requirements
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3989009)