Computing the Strength of a Graph

DOI10.1137/0220040MaRDI QIDQ3978173zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 56092
• scientific article; zbMATH DE number 4029614
• scientific article; zbMATH DE number 804042
• scientific article; zbMATH DE number 7250383
• Computing an irregularity strength of selected graphs
• Bounds for the strength of graphs
• Computational complexity of graphs
• On the Strength and Independence Number of Graphs
• On the strength and domination number of graphs
• Computing the strong alliance polynomial of a graph

Cited in

(20)

• 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
• Computational implementation of Fujishige's graph realizability algorithm
• A faster parametric minimum-cut algorithm
• A faster algorithm for computing the strength of a network
• Improving graph partitions using submodular functions.
• Strength of a graph and packing of trees and branchings
• Games induced by the partitioning of a graph
• On some algorithmic aspects of hypergraphic matroids
• Network reinforcement
• Graphic submodular function minimization: a graphic approach and applications
• A linear programming approach to increasing the weight of all minimum spanning trees
• scientific article; zbMATH DE number 4029614 (Why is no real title available?)
• scientific article; zbMATH DE number 56092 (Why is no real title available?)
• Computing weighted strength and applications to partitioning
• scientific article; zbMATH DE number 804042 (Why is no real title available?)
• Computing the largest bond of a graph
• Optimal hierarchical clustering on a graph
• Finding the maximum subgraph of prescribed strength
• A faster algorithm for computing the principal sequence of partitions of a graph

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

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