2026-07-24T03:33:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23244 2025-10-27T10:36:10Z ddc:004 open_access

Planar Network Diversion Bentert, Matthias Drange, Pål Grønås Fomin, Fedor V. Simonnes, Steinar Minimal cuts Bridges Network interdiction Algorithm engineering Network Diversion is a graph problem that has been extensively studied in both the network-analysis and operations-research communities as a measure of how robust a network is against adversarial disruption. In Network Diversion we want to enforce all s-t-paths through a specific edge b by removing edges from G. This problem is especially well motivated in transportation networks, which are often assumed to be planar. Motivated by this and recent theoretical advances for Network Diversion on planar input graphs, we develop a fast O(n log n) time algorithm and present a practical implementation of this algorithm that is able to solve instances with millions of vertices in a matter of seconds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and Pål Grønås Drange and Fedor V. Fomin and Steinar Simonnes 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.6 urn:nbn:de:0030-drops-232448 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.6 eng https://creativecommons.org/licenses/by/4.0/legalcode