The minimum vulnerability problem

DOI10.1007/S00453-014-9927-ZMaRDI QIDQ487032zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1487883 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A new approach to the maximum-flow problem
• Approximability of capacitated network design
• Approximation algorithms for the covering Steiner problem
• Beyond the flow decomposition barrier
• Capacitated network design on undirected graphs
• Finding paths with minimum shared edges
• On fixed cost \(k\)-flow problems
• On network design problems: fixed cost flows and the covering steiner problem
• The minimum vulnerability problem

Cited in

(12)

• The parameterized complexity of the minimum shared edges problem
• The minimum vulnerability problem on graphs
• 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)