Interdiction problems on planar graphs

DOI10.1016/j.dam.2015.05.036zbMath1327.05234arXiv1305.1407OpenAlexW1835927266MaRDI QIDQ897609

Aaron Schild, Feng Pan

Publication date: 7 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.1407

zbMATH Keywords

planar graphsmaximum matchingapproximation schememaximum flowinterdictioncrossing gadget

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (9)

Interdicting facilities in tree networks ⋮ A mixed-integer programming approach for locating jamming devices in a flow-jamming attack ⋮ Fractals for Kernelization Lower Bounds ⋮ Unnamed Item ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Scalable min-max multi-objective cyber-security optimisation over probabilistic attack graphs ⋮ The complexity of finding small separators in temporal graphs ⋮ On the hardness of covering-interdiction problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching interdiction
• Graph minors. III. Planar tree-width
• On short paths interdiction problems: Total and node-wise limited interdiction
• Network flow interdiction on planar graphs
• The k most vital arcs in the shortest path problem
• S-functions for graphs
• Deterministic network interdiction
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
• On budget-constrained flow improvement.
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Approximation algorithms for NP-complete problems on planar graphs
• Shortest-path network interdiction
• Packing Interdiction and Partial Covering Problems
• The network inhibition problem
• A note on shortest path, assignment, and transportation problems
• Optimal interdiction policy for a flow network

This page was built for publication: Interdiction problems on planar graphs