Planar Network Diversion
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929727329009664 |
|---|---|
| author | Bentert, Matthias Drange, Pål Grønås Fomin, Fedor V. Simonnes, Steinar |
| author_facet | Bentert, Matthias Drange, Pål Grønås Fomin, Fedor V. Simonnes, Steinar |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16714 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Planar Network Diversion Bentert, Matthias Drange, Pål Grønås Fomin, Fedor V. Simonnes, Steinar Data Structures and Algorithms Computational Geometry F.2.2 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. |
| title | Planar Network Diversion |
| topic | Data Structures and Algorithms Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2502.16714 |