A faster algorithm for computing the strength of a network

DOI10.1016/0020-0190(94)90013-2MaRDI QIDQ1318743zbMATH OpenOpenAlexFDO

Authors Eddie Cheng, William H. Cunningham

Publication date 5 April 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)90013-2

zbMATH Keywords

network survivabilitystrengthratio minimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 56092
• scientific article; zbMATH DE number 804042
• Optimal attack and reinforcement of a network
• Computing weighted strength and applications to partitioning
• Computing the Strength of a Graph

Cites work

• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• Computing the Strength of a Graph
• Connectivity and edge-disjoint spanning trees
• Optimal attack and reinforcement of a network
• Separating from the dominant of the spanning tree polytope

Cited in

(22)

• Computing weighted strength and applications to partitioning
• Network strength games: the core and the nucleolus
• A note on optimal covering augmentation for graphic polymatroids.
• A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees
• A linear programming approach to increasing the weight of all minimum spanning trees
• Modulus for bases of matroids
• Improving graph partitions using submodular functions.
• A faster algorithm for computing the principal sequence of partitions of a graph
• A kind of conditional connectivity of Cayley graphs generated by wheel graphs
• On some algorithmic aspects of hypergraphic matroids
• On the \(k\)-cut problem
• Graphic submodular function minimization: a graphic approach and applications
• Comparison of three approaches to studying stability of solutions to problems of discrete optimization and computational geometry
• Transforming a graph into a 1-balanced graph
• A new algorithm for the intersection of a line with the independent set polytope of a matroid
• scientific article; zbMATH DE number 2230273 (Why is no real title available?)
• Optimal hierarchical clustering on a graph
• Finding the maximum subgraph of prescribed strength
• Optimal attack and reinforcement of a network
• Network reinforcement
• Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness
• Stability of solutions in problems of computational geometry

This page was built for publication: A faster algorithm for computing the strength of a network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1318743)