@TECHREPORT{R-96-25,
PSURL = {/publications/cgi-bin/tr-fetch.pl?r-96-25+ps},
NUMBER = {R-96-25},
INSTITUTION = ida,
ADDRESS = idaaddr,
YEAR = {1996},
AUTHOR = {Jonsson, Peter and Drakengren, Thomas},
TITLE = {RCC-5 and its Tractable Subclasses},
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-96-25+abstr},
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.}