The minimum vulnerability problem

DOI10.1007/s00453-014-9927-zzbMath1306.05113OpenAlexW2021441806MaRDI QIDQ487032

Sadra Yazdanbod, Ashkan Norouzi-Fard, Sepehr Assadi, Ehsan Emamjomeh-Zadeh, 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

network designapproximation algorithmsinapproximabilityshared edges

Mathematics Subject Classification ID

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

Related Items

Probability Distributions on Partially Ordered Sets and Network Interdiction Games ⋮ An iterative security game for computing robust and adaptive network flows ⋮ Approximate separable multichoice optimization over monotone systems ⋮ Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications ⋮ Unnamed Item ⋮ The complexity of routing with collision avoidance ⋮ Parameterized shifted combinatorial optimization ⋮ The unimodular intersection problem ⋮ The parameterized complexity of the minimum shared edges problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding paths with minimum shared edges
• 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
• On Fixed Cost k-Flow Problems
• A new approach to the maximum-flow problem
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Approximation algorithms for the covering Steiner problem
• The Minimum Vulnerability Problem

This page was built for publication: The minimum vulnerability problem