Optimal attack and reinforcement of a network
From MaRDI portal
Publication:3767103
DOI10.1145/3828.3829zbMath0629.90034OpenAlexW2065320942MaRDI 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 algorithmpolymatroidsweight of an edgeminimum cutsstrongly polynomial algorithmsratio minimizationoptimal attacknonnegative edge-weighted network
Analysis of algorithms and problem complexity (68Q25) Applications of mathematical programming (90C90) Deterministic network models in operations research (90B10)
Related Items
Edge vulnerability parameters of split graphs, Minimum cost subpartitions in graphs, Strength of a graph and packing of trees and branchings, Network Elicitation in Adversarial Environment, A faster algorithm for computing the principal sequence of partitions of a graph, Strength and fractional arboricity of complementary graphs, Separation of partition inequalities with terminals, Optimization of computations, Computing Weighted Strength and Applications to Partitioning, Design of survivable IP-over-optical networks, On two-connected subgraph polytopes, Generalized polymatroids and submodular flows, Strength and reinforcement of a network and tree packing, A Brief Account on the Development and Future Research Directions of Connectivity Properties of Interconnection Networks, Hypergraphic submodular function minimization, Generalized max flows and augmenting paths, Optimal hierarchical clustering on a graph, Group Connectivity, Strongly Z_m-Connectivity, and Edge Disjoint Spanning Trees, Spectral radius and edge‐disjoint spanning trees, Spanning tree modulus for secure broadcast games, Supereulerian regular matroids without small cocircuits, Hitting a path: a generalization of weighted connectivity via game theory, Graph rigidity properties of Ramanujan graphs, Risk‐averse optimization and resilient network flows, Strategic Network Formation with Attack and Immunization, Approximation algorithms for \(k\)-hurdle problems, Games induced by the partitioning of a graph, Edge-disjoint spanning trees and eigenvalues of regular graphs, A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees, Theory of Principal Partitions Revisited, Graphic Submodular Function Minimization: A Graphic Approach and Applications, Degree sequences and graphs with disjoint spanning trees, Packing and covering with integral feasible flows in integral supply-demand networks, New polyhedral and algorithmic results on greedoids, Spanning trees: A survey, Fast approximation of matroid packing and covering, A linear programming approach to increasing the weight of all minimum spanning trees, A kind of conditional connectivity of Cayley graphs generated by wheel graphs, LP Relaxation and Tree Packing for Minimum $k$-Cut, Characterizations of strength extremal graphs, On the \(k\)-cut problem, Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs, Approximating \(k\)-cuts using network strength as a Lagrangean relaxation, Optimal design and defense of networks under link attacks, Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure, Security games on matroids, On minimum 3-cuts and approximating k-cuts using Cut Trees, Polarity and the complexity of the shooting experiment, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, Transitions in geometric minimum spanning trees, Separating from the dominant of the spanning tree polytope, Brick partitions of graphs, Fractional arboricity, strength, and principal partitions in graphs and matroids, A proof of the molecular conjecture, Greedy splitting algorithms for approximating multiway partition problems, A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions, Characterization of removable elements with respect to having \(k\) disjoint bases in a matroid, Packing the Steiner trees of a graph, 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, Approximation Algorithms for k-Hurdle Problems, Non-preemptive tree packing, Network strength games: the core and the nucleolus, Non-preemptive tree packing, Small Submatroids in Random Matroids, Computing the binding number of a graph, Network Topology Vulnerability/Cost Trade-Off: Model, Application, and Computational Complexity, Unnamed Item, Spanning tree packing number and eigenvalues of graphs with given girth, Game-theoretic Robustness of Many-to-one Networks, Minimizing symmetric submodular functions, \(k\)-edge connected polyhedra on series-parallel graphs, Degree sequence realizations with given packing and covering of spanning trees, On some algorithmic aspects of hypergraphic matroids, Network reinforcement, Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut, Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness, How Do You Defend a Network?, A note on optimal covering augmentation for graphic polymatroids., A faster algorithm for computing the strength of a network, Separation of partition inequalities for the \((1,2)\)-survivable network design problem, Modelling and simulations for DDoS attacks mitigation in identifier–locator split network
