Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917040100474880 |
|---|---|
| author | Wallisch, Christian Fluschnik, Till Kellerhals, Leon |
| author_facet | Wallisch, Christian Fluschnik, Till Kellerhals, Leon |
| contents | We study a network design problem motivated by the challenge of placing wildlife crossings to reconnect fragmented habitats of animal species, which is among the 17 goals towards sustainable development by the UN: Given a graph, whose vertices represent the fragmented habitat areas and whose edges represent possible green bridge locations (with costs), and the habitable vertex set for each species' habitat, the goal is to find the cheapest set of edges such that each species' habitat is sufficiently connected. We focus on the established variant where a habitat is considered sufficiently connected if it has diameter two in the solution and study its complexity in cases justified by our setting namely small habitat sizes on planar graphs and graphs of small maximum degree $Δ$. We provide efficient algorithms and NP-hardness results for different values of $Δ$ and maximum habitat sizes on general and planar graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21540 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs Wallisch, Christian Fluschnik, Till Kellerhals, Leon Data Structures and Algorithms Computational Complexity We study a network design problem motivated by the challenge of placing wildlife crossings to reconnect fragmented habitats of animal species, which is among the 17 goals towards sustainable development by the UN: Given a graph, whose vertices represent the fragmented habitat areas and whose edges represent possible green bridge locations (with costs), and the habitable vertex set for each species' habitat, the goal is to find the cheapest set of edges such that each species' habitat is sufficiently connected. We focus on the established variant where a habitat is considered sufficiently connected if it has diameter two in the solution and study its complexity in cases justified by our setting namely small habitat sizes on planar graphs and graphs of small maximum degree $Δ$. We provide efficient algorithms and NP-hardness results for different values of $Δ$ and maximum habitat sizes on general and planar graphs. |
| title | Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2510.21540 |