Edge-Connectivity Augmentation with Partition Constraints

DOI10.1137/S0895480197324700zbMath0922.05034OpenAlexW1971486128MaRDI QIDQ4255815

Harold N. Gabow, Zoltán Szigeti, Tibor Jordán, Jörgen Bang-Jensen

Publication date: 27 June 1999

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

Full work available at URL: https://doi.org/10.1137/s0895480197324700

zbMATH Keywords

partitionalgorithmrigiditybiconnectivityedge-connection augmentation problemsplitting off techniques

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Connectivity (05C40)

Related Items (17)

Smallest bipartite bridge-connectivity augmentation ⋮ Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs ⋮ A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case ⋮ Augmenting the rigidity of a graph in \(\mathbb R^{2}\) ⋮ Distance and connectivity measures in permutation graphs ⋮ Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph ⋮ Edge-Connectivity Augmentations of Graphs and Hypergraphs ⋮ Edge-connectivity of permutation hypergraphs ⋮ Splitting off edges between two subsets preserving the edge-connectivity of the graph. ⋮ 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 ⋮ The bridge-connectivity augmentation problem with a partition constraint ⋮ Bipartition constrained edge-splitting in directed graphs ⋮ Connectivity interdiction ⋮ The \((2, k)\)-connectivity augmentation problem: algorithmic aspects ⋮ Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph

This page was built for publication: Edge-Connectivity Augmentation with Partition Constraints