<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Alexander Westcott,
  • Charl Ras

摘要

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.