The maximum residual flow problem: NP‐hardness with two‐arc destruction

DOI10.1002/NET.20188MaRDI QIDQ5434585zbMATH OpenOpenAlexFDO

Authors R. Chandrasekaran, Donglei Du

Publication date 7 January 2008

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20188

zbMATH Keywords

arc destructioncapacity representativeresidual flow NP-hard

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Maximizing residual flow under an arc destruction
• Complexity of a classical flow restoration problem
• Reserving resilient capacity in a network
• scientific article; zbMATH DE number 4041594
• Complexity and approximability of the maximum flow problem with minimum quantities

Cites work

• Geometric algorithms and combinatorial optimization

Cited in

(10)

• Protection of flows under targeted attacks
• Robust flows over time: models and complexity results
• On the power of randomization in network interdiction
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
• The complexity of computing a robust flow
• The value of information in stochastic maximum flow problems
• Maximizing residual flow under an arc destruction
• Robust flows with adaptive mitigation
• Robust static and dynamic maximum flows
• Stronger hardness for maximum robust flow and randomized network interdiction

This page was built for publication: The maximum residual flow problem: NP‐hardness with two‐arc destruction

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