The minimum vulnerability problem

DOI10.1007/S00453-014-9927-ZzbMATH Open1306.05113OpenAlexW2021441806MaRDI QIDQ487032FDOQ487032

Authors: Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Ashkan Norouzi-Fard, Sadra Yazdanbod, Hamid Zarrabi-Zadeh 

Publication date: 19 January 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9927-z

Recommendations

• The minimum vulnerability problem
• The minimum vulnerability problem on specific graph classes
• The minimum vulnerability problem on graphs
• Finding paths with minimum shared edges
• Finding paths with minimum shared edges

zbMATH Keywords

approximation algorithmsinapproximabilitynetwork designshared edges

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Paths and cycles (05C38) Network design and communication in computer systems (68M10)

Cites Work

• Title not available (Why is that?)
• Capacitated network design on undirected graphs
• On network design problems: fixed cost flows and the covering steiner problem
• Approximability of capacitated network design
• Beyond the flow decomposition barrier
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Title not available (Why is that?)
• A new approach to the maximum-flow problem
• Finding paths with minimum shared edges
• Title not available (Why is that?)
• The minimum vulnerability problem
• Approximation algorithms for the covering Steiner problem
• On fixed cost \(k\)-flow problems

Cited In (12)

• The minimum vulnerability problem on graphs
• The parameterized complexity of the minimum shared edges problem
• An iterative security game for computing robust and adaptive network flows
• Approximate separable multichoice optimization over monotone systems
• The minimum vulnerability problem on specific graph classes
• The complexity of routing with collision avoidance
• The minimum vulnerability problem
• Extension complexity, MSO logic, and treewidth
• The unimodular intersection problem
• Probability Distributions on Partially Ordered Sets and Network Interdiction Games
• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
• Finding paths with minimum shared edges

This page was built for publication: The minimum vulnerability problem

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