On the Structure of Minimum-Weight k-Connected Spanning Networks

DOI10.1137/0403027zbMath0708.05053OpenAlexW2159586130MaRDI QIDQ3490035

Bienstock, Daniel, Clyde l. Monma, Ernest F. Brickell

Publication date: 1990

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

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

zbMATH Keywords

communication networkssurvivabilitycomplete graphminimum-weight k-connected spanning subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Connectivity (05C40)

Related Items

Minimum Cost ≤k Edges Connected Subgraph Problems, Property testing on \(k\)-vertex-connectivity of graphs, On shredders and vertex connectivity augmentation, The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points., On the Steiner 2-edge connected subgraph polytope, Minimum-weight two-connected spanning networks, A branch-and-cut algorithm for the k-edge connected subgraph problem, On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem, Extremal graphs in connectivity augmentation, On shortest three-edge-connected Steiner networks with Euclidean distance, \(k\)-edge connected polyhedra on series-parallel graphs