Augmenting Graphs to Meet Edge-Connectivity Requirements
From MaRDI portal
Publication:3989009
DOI10.1137/0405003zbMath0782.05054OpenAlexW4367329880WikidataQ56519177 ScholiaQ56519177MaRDI QIDQ3989009
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
Graph theory (including graph drawing) in computer science (68R10) Operations research and management science (90B99) Connectivity (05C40)
Related Items
Increasing digraph arc-connectivity by arc addition, reversal and complement, Augmenting weighted graphs to establish directed point-to-point connectivity, A note on minimizing submodular functions, Extension to Even Triangulations, Network design with edge-connectivity and degree constraints, Highly edge-connected detachments of graphs and digraphs, Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs, Structured Connectivity Augmentation, Triangulating planar graphs while minimizing the maximum degree, Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs, Structures of subpartitions related to a submodular function minimization, Robustness and Strong Attack Tolerance of Low-Diameter Networks, Covering symmetric supermodular functions with graph edges: a short proof of a theorem of Benczúr and Frank, Structured Connectivity Augmentation, Degree sequence for \(k\)-arc strongly connected multiple digraphs, The Generalized Terminal Backup Problem, 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, Characterizing and recognizing generalized polymatroids, A New Approach to Splitting-Off, 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, Characterization of Digraphic Sequences with Strongly Connected Realizations, A survey of parameterized algorithms and the complexity of edge modification, Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems, On the minimum local-vertex-connectivity augmentation in graphs, Approximating node-connectivity augmentation problems, Optimal bi-level augmentation for selective! enhancing graph connectivity with applications, Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph, Approximating Minimum Cost Connectivity Orientation and Augmentation, A Survey on Covering Supermodular Functions, Edge-Connectivity Augmentations of Graphs and Hypergraphs, Edge splitting and connectivity augmentation in directed hypergraphs., Path-contractions, edge deletions and connectivity preservation, Splitting off edges between two subsets preserving the edge-connectivity of the graph., Augmenting the edge connectivity of planar straight line graphs to three, On shredders and vertex connectivity augmentation, Testing Eulerianity and connectivity in directed sparse graphs, A unifying approach to splitting-off, Shorter tours and longer detours: uniform covers and a bit beyond, Testing \(k\)-edge-connectivity of digraphs, Augmenting edge-connectivity between vertex subsets, Efficiently Realizing Interval Sequences, Multigraph augmentation under biconnectivity and general edge-connectivity requirements, Splitting off operation for binary matroids and its applications, Tight approximation algorithm for connectivity augmentation problems, Connectivity augmentation in planar straight line graphs, On the cycle augmentation problem: hardness and approximation algorithms, Covering symmetric semi-monotone functions, Minimizing a monotone concave function with laminar covering constraints, Strongly connectable digraphs and non-transitive dice, On a theorem of Mader, An algorithm to increase the node-connectivity of a digraph by one, Submodular functions in graph theory, Augmenting the Edge‐Connectivity of a Hypergraph by Adding a Multipartite Graph, Edge-splittings preserving local edge-connectivity of graphs, Graph connectivity and its augmentation: Applications of MA orderings, Local edge-connectivity augmentation in hypergraphs is NP-complete, Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks, Independence free graphs and vertex connectivity augmentation, A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows, A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation, Bipartition constrained edge-splitting in directed graphs, Connectivity interdiction, Augmenting trees so that every three vertices lie on a cycle, Edge-connectivity augmentation of graphs over symmetric parity families, Extremal graphs in connectivity augmentation, Vertex-weighted realizations of graphs, The \((2, k)\)-connectivity augmentation problem: algorithmic aspects, Composed degree-distance realizations of graphs, Posimodular function optimization, Fast exact algorithms for survivable network design with uniform requirements, Realization problems on reachability sequences, A new contraction technique with applications to congruency-constrained cuts, Composed degree-distance realizations of graphs, Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs, Making bidirected graphs strongly connected, Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings, Supermodularity in Unweighted Graph Optimization III: Highly Connected Digraphs, Inapproximability of survivable networks, Approximating Source Location and Star Survivable Network Problems, On the minor-minimal 2-connected graphs having a fixed minor, Vertex fusion under distance constraints, Path-Contractions, Edge Deletions and Connectivity Preservation, Polyhedral structure of submodular and posi-modular systems, Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph, On integer network synthesis problem with tree-metric cost, Decreasing minimization on M-convex sets: algorithms and applications, Relaxed and approximate graph realizations
