On the hardness of covering-interdiction problems

DOI10.1016/j.tcs.2021.04.007zbMath1503.68219OpenAlexW3153827225MaRDI QIDQ2031041

Stefan Ruzika, Nicolas Fröhlich

Publication date: 8 June 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.04.007

zbMATH Keywords

complexitypolynomial hierarchynetwork interdictionlocation planning

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Spatial models in economics (91B72)

Related Items (1)

Interdicting facilities in tree networks

Cites Work

• The budget constrained \(r\)-interdiction median problem with capacity expansion
• Interdiction problems on planar graphs
• On short paths interdiction problems: Total and node-wise limited interdiction
• Network flow interdiction on planar graphs
• Most vital links and nodes in weighted networks
• Finding the most vital arcs in a network
• Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems
• Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives
• Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
• The Maximum Coverage Location Problem
• Packing Interdiction and Partial Covering Problems
• Computational Complexity

This page was built for publication: On the hardness of covering-interdiction problems