Augmenting Graphs to Meet Edge-Connectivity Requirements
From MaRDI portal
Publication:3989009
DOI10.1137/0405003zbMath0782.05054WikidataQ56519177 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
combinatorial optimization; polynomial time algorithm; polymatroids; edge-connectivity; splitting theorems
68R10: Graph theory (including graph drawing) in computer science
90B99: Operations research and management science
05C40: Connectivity
Related Items
Highly edge-connected detachments of graphs and digraphs, Bipartition constrained edge-splitting in directed graphs, Augmenting trees so that every three vertices lie on a cycle, Submodular functions in graph theory, Graph connectivity and its augmentation: Applications of MA orderings, 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, On shredders and vertex connectivity augmentation, Tight approximation algorithm for connectivity augmentation problems, Minimizing a monotone concave function with laminar covering constraints, An algorithm to increase the node-connectivity of a digraph by one, Edge-connectivity augmentation of graphs over symmetric parity families, 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, Independence free graphs and vertex connectivity augmentation, On the minor-minimal 2-connected graphs having a fixed minor, Polyhedral structure of submodular and posi-modular systems, 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, A New Approach to Splitting-Off, Unnamed Item
