
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. 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.
Network interdiction, Computational Geometry (cs.CG), FOS: Computer and information sciences, Minimal cuts, Computer Science - Data Structures and Algorithms, Computer Science - Computational Geometry, Data Structures and Algorithms (cs.DS), F.2.2, Bridges, Algorithm engineering, ddc: ddc:004
Network interdiction, Computational Geometry (cs.CG), FOS: Computer and information sciences, Minimal cuts, Computer Science - Data Structures and Algorithms, Computer Science - Computational Geometry, Data Structures and Algorithms (cs.DS), F.2.2, Bridges, Algorithm engineering, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
