Abstract

RCC8 Is Polynomial on Networks of Bounded Treewidth
RCC8 Is Polynomial on Networks of Bounded Treewidth
Manuel Bodirsky, Stefan Wölfl
We construct an homogeneous (and omega-categorical) representation of the relation algebra RCC8, which is one of the fundamental formalisms for spatial reasoning. As a consequence we obtain that the network consistency problem for RCC8 can be solved in polynomial time for networks of bounded treewidth.