Jonsson, P. and Drakengren, T. (1996). RCC-5 and its Tractable Subclasses. Technical Report LiTH-IDA-R-96-25, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: We investigate the computational properties of the spatial algebra RCC-5 which is a restricted version of the RCC framework. The satisfiability problem for RCC-5 is known to be NP-complete but not much is known about its approximately four billion subclasses. We provide a complete classification of satisfiability for all these subclasses into polynomial and NP-complete respectively. In the process, we identify all maximal tractable subalgebras which are four in total.
CS Dept TR Overview