An exact algorithm for disaster-resilience augmentation of planar straight-line graphs

Alexander Westcott and Charl Ras ()
Additional contact information
Alexander Westcott: University of Melbourne
Charl Ras: University of Melbourne

Journal of Global Optimization, 2025, vol. 92, issue 2, No 10, 483-508

Abstract: Abstract We consider the problem of adding a minimum length set of edges to a geometric graph so that the resultant graph is resilient against partition from the effect of a single disaster. Disasters are modeled by discs of given maximum radius, and a disaster destroys all edges intersecting its interior. It is assumed that the input and output graphs are planar with a straight-line embedding. We provide a computationally simple characterisation of feasible input instances in terms of the convex hull of the given graph, and present a fast ILP algorithm for generating optimal solutions. We also perform a computational study which shows that our algorithm is able to solve randomly generated instances with hundreds of nodes.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-024-01459-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:92:y:2025:i:2:d:10.1007_s10898-024-01459-0

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-024-01459-0

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().