Computing the Strength of a Graph

DOI10.1137/0220040zbMath0743.90045OpenAlexW2062931369MaRDI QIDQ3978173

Dan Gusfield

Publication date: 25 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph vulnerabilityparametric flow in a bipartite networkpolymatroid greedy algorithmstrength of a group

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Graph theory (05C99)

Related Items (14)

Strength of a graph and packing of trees and branchings ⋮ A faster algorithm for computing the principal sequence of partitions of a graph ⋮ Computing Weighted Strength and Applications to Partitioning ⋮ Optimal hierarchical clustering on a graph ⋮ Games induced by the partitioning of a graph ⋮ Improving graph partitions using submodular functions. ⋮ Graphic Submodular Function Minimization: A Graphic Approach and Applications ⋮ A linear programming approach to increasing the weight of all minimum spanning trees ⋮ 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 ⋮ On some algorithmic aspects of hypergraphic matroids ⋮ Network reinforcement ⋮ A faster parametric minimum-cut algorithm ⋮ A faster algorithm for computing the strength of a network

This page was built for publication: Computing the Strength of a Graph