---
title: "Reasoning about Connectivity Constraints"
authors:
  - "Christian Bessière"
  - "Emmanuel Hebrard"
  - "George Katsirelos"
  - "Toby Walsh"
doi: ""
url: "https://ijcai.org/proceedings/2015/364"
pdf: "https://ijcai.org/proceedings/2015/0364.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "2568-2573"
track: "Special Track on Computational Sustainability"
keywords:
---

# Reasoning about Connectivity Constraints

Christian Bessière, Emmanuel Hebrard, George Katsirelos, Toby Walsh

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 2568-2573.

## Abstract

Many problems in computational sustainability involve constraints on connectivity. When designing a new wildlife corridor, we need it to be geographically connected. When planning the harvest of a forest, we need new areas to harvest to be connected to areas that have already been harvested so we can access them easily. And when town planning, we need to connect new homes to the existing utility infrastructure. To reason about connectivity, we propose a new family of global connectivity constraints. We identify when these constraints can be propagated tractably, and give some efficient, typically linear time propagators for when this is the case. We report results on several benchmark problems which demonstrate the efficiency of our propagation algorithms and the promise offered by reasoning globally about connectivity.