DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2025.6

Planar Network Diversion

Authors: Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, and Steinar Simonnes

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract

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.

Cite as

Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, and Steinar Simonnes. Planar Network Diversion. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.SEA.2025.6,
  author =	{Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Fomin, Fedor V. and Simonnes, Steinar},
  title =	{{Planar Network Diversion}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.6},
  URN =		{urn:nbn:de:0030-drops-232448},
  doi =		{10.4230/LIPIcs.SEA.2025.6},
  annote =	{Keywords: Minimal cuts, Bridges, Network interdiction, Algorithm engineering}
}

Search Results

Documents authored by Simonnes, Steinar

Planar Network Diversion

Abstract

Cite as

Thanks for your feedback!

Could not send message