Optimal attack and reinforcement of a network
From MaRDI portal
Publication:3767103
DOI10.1145/3828.3829zbMath0629.90034MaRDI QIDQ3767103
Publication date: 1985
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3828.3829
greedy algorithm; polymatroids; weight of an edge; minimum cuts; strongly polynomial algorithms; ratio minimization; optimal attack; nonnegative edge-weighted network
68Q25: Analysis of algorithms and problem complexity
90C90: Applications of mathematical programming
90B10: Deterministic network models in operations research
Related Items
Small Submatroids in Random Matroids, Approximation Algorithms for k-Hurdle Problems, Unnamed Item, Design of survivable IP-over-optical networks, Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure, Polarity and the complexity of the shooting experiment, 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, Generalized polymatroids and submodular flows, Transitions in geometric minimum spanning trees, Separating from the dominant of the spanning tree polytope, Fractional arboricity, strength, and principal partitions in graphs and matroids, Minimizing symmetric submodular functions, A faster algorithm for computing the strength of a network, Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness, A note on optimal covering augmentation for graphic polymatroids., Greedy splitting algorithms for approximating multiway partition problems, Computing the binding number of a graph, Separation of partition inequalities for the \((1,2)\)-survivable network design problem, Strength of a graph and packing of trees and branchings, Strength and fractional arboricity of complementary graphs, Optimization of computations, On two-connected subgraph polytopes, On the \(k\)-cut problem, Edge vulnerability parameters of split graphs, Separation of partition inequalities with terminals, Approximating \(k\)-cuts using network strength as a Lagrangean relaxation, \(k\)-edge connected polyhedra on series-parallel graphs, Network reinforcement, Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, A linear programming approach to increasing the weight of all minimum spanning trees, Packing and covering with integral feasible flows in integral supply-demand networks, Strength and reinforcement of a network and tree packing
