Planar Network Diversion
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |