---
title: "Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints"
authors:
  - "Nouhad Amaneddine"
  - "Jean-François Condotta"
  - "Michael Sioutis"
doi: ""
url: "https://ijcai.org/proceedings/2013/110"
pdf: "https://ijcai.org/proceedings/2013/0110.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "696-701"
track: ""
keywords:
---

# Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints

Nouhad Amaneddine, Jean-François Condotta, Michael Sioutis

*Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence*, pages 696-701.

## Abstract

The Interval Algebra (IA) and a subset of the Region Connection Calculus (RCC), namely RCC-8, are the dominant Artificial Intelligence approaches for representing and reasoning about qualitative temporal and topological relations respectively. Such qualitative information can be formulated as a Qualitative Constraint Network (QCN). In this paper, we focus on the minimal labeling problem (MLP) and we propose an algorithm to efficiently derive all the feasible base relations of a QCN. Our algorithm considers chordal QCNs and a new form of partial consistency. Further, the proposed algorithm uses tractable subclasses of relations having a specific patchwork property for which closure under weak composition implies the consistency of the input QCN. Experimentations with QCNs of IA and RCC-8 show the importance and efficiency of this new approach.