Augmenting Graphs to Meet Edge-Connectivity Requirements

DOI10.1137/0405003zbMATH Open0782.05054OpenAlexW4367329880WikidataQ56519177 ScholiaQ56519177MaRDI QIDQ3989009FDOQ3989009

Authors: András Frank 

Publication date: 28 June 1992

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/69ec8e6092e3e1db81af9af1567f6155dea9f3da

Recommendations

• scientific article; zbMATH DE number 1104329
• 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.

zbMATH Keywords

combinatorial optimizationpolynomial time algorithmedge-connectivitysplitting theoremspolymatroids

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Operations research and management science (90B99)

Cited In (96)

• An algorithm to increase the node-connectivity of a digraph by one
• Title not available (Why is that?)
• Characterizing and recognizing generalized polymatroids
• Edge splitting and connectivity augmentation in directed hypergraphs.
• Approximating source location and star survivable network problems
• Extension to Even Triangulations
• Local edge-connectivity augmentation in hypergraphs is NP-complete
• Network design with edge-connectivity and degree constraints
• Edge-Connectivity Augmentation with Partition Constraints
• Increasing digraph arc-connectivity by arc addition, reversal and complement
• The \((2, k)\)-connectivity augmentation problem: algorithmic aspects
• Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
• Inapproximability of survivable networks
• Highly edge-connected detachments of graphs and digraphs
• A New Approach to Splitting-Off
• Fast exact algorithms for survivable network design with uniform requirements
• Testing \(k\)-edge-connectivity of digraphs
• Splitting off edges between two subsets preserving the edge-connectivity of the graph.
• Structured connectivity augmentation
• Structured connectivity augmentation
• Testing Eulerianity and connectivity in directed sparse graphs
• On shredders and vertex connectivity augmentation
• Tight approximation algorithm for connectivity augmentation problems
• A note on minimizing submodular functions
• Polyhedral structure of submodular and posi-modular systems
• Minimal edge-coverings of pairs of sets
• Graph orientations with set connectivity requirements
• Augmenting edge-connectivity between vertex subsets
• Connectivity interdiction
• Approximating node-connectivity augmentation problems
• A survey of parameterized algorithms and the complexity of edge modification
• On the minor-minimal 2-connected graphs having a fixed minor
• Independence free graphs and vertex connectivity augmentation
• Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
• A unifying approach to splitting-off
• Edge-splittings preserving local edge-connectivity of graphs
• Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph
• Multigraph augmentation under biconnectivity and general edge-connectivity requirements
• Graph connectivity and its augmentation: Applications of MA orderings
• Triangulating planar graphs while minimizing the maximum degree
• A Survey on Covering Supermodular Functions
• Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
• Robustness and strong attack tolerance of low-diameter networks
• Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs
• Edge-connectivity augmentation of graphs over symmetric parity families
• Minimum augmentation of a tree to a K-edge-connected graph
• Vertex fusion under distance constraints
• Structures of subpartitions related to a submodular function minimization
• A polyhedral approach to planar augmentation and related problems
• Augmenting the edge connectivity of planar straight line graphs to three
• Connectivity augmentation in planar straight line graphs
• On a theorem of Mader
• Edge-connectivity augmentations of~graphs~and~hypergraphs
• Splitting off operation for binary matroids and its applications
• Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph
• Efficiently realizing interval sequences
• Submodular functions in graph theory
• Path-contractions, edge deletions and connectivity preservation
• Approximating Minimum Cost Connectivity Orientation and Augmentation
• A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem
• On the minimum local-vertex-connectivity augmentation in graphs
• Minimizing a monotone concave function with laminar covering constraints
• Extremal graphs in connectivity augmentation
• Strongly connectable digraphs and non-transitive dice
• A new contraction technique with applications to congruency-constrained cuts
• How to make a strongly connected digraph two-connected
• Covering symmetric semi-monotone functions
• Relaxed and approximate graph realizations
• The generalized terminal backup problem
• Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks
• Augmenting weighted graphs to establish directed point-to-point connectivity
• Bipartition constrained edge-splitting in directed graphs
• On integer network synthesis problem with tree-metric cost
• A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
• Optimal bi-level augmentation for selective! enhancing graph connectivity with applications
• Path-contractions, edge deletions and connectivity preservation
• Covering symmetric supermodular functions with graph edges: a short proof of a theorem of Benczúr and Frank
• Posimodular function optimization
• Realization problems on reachability sequences
• Vertex-weighted realizations of graphs
• Complexity of (arc)-connectivity problems involving arc-reversals or deorientations
• Characterization of digraphic sequences with strongly connected realizations
• Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph
• Shorter tours and longer detours: uniform covers and a bit beyond
• Making bidirected graphs strongly connected
• Edge-connectivity augmentation of simple graphs
• Degree sequence for \(k\)-arc strongly connected multiple digraphs
• Supermodularity in unweighted graph optimization. I: Branchings and matchings
• Composed degree-distance realizations of graphs
• Composed degree-distance realizations of graphs
• Augmenting trees so that every three vertices lie on a cycle
• On the cycle augmentation problem: hardness and approximation algorithms
• Fault-tolerant graph realizations in the congested clique
• Supermodularity in unweighted graph optimization. III: Highly connected digraphs
• Decreasing minimization on M-convex sets: algorithms and applications
• A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation

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)