RCC8 Is Polynomial on Networks of Bounded Treewidth

Bodirsky, Manuel; Wölfl, Stefan

doi:10.5591/978-1-57735-516-8/IJCAI11-133

RCC8 Is Polynomial on Networks of Bounded Treewidth

Manuel Bodirsky, Stefan Wölfl

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 756-760.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-133

Abstract

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.

Manuel Bodirsky, and Stefan Wölfl. 2011. RCC8 Is Polynomial on Networks of Bounded Treewidth. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 756–760. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-133

@inproceedings{ijcai2011p133,
  title     = {RCC8 Is Polynomial on Networks of Bounded Treewidth},
  author    = {Bodirsky, Manuel and Wölfl, Stefan},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {756--760},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-133},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-133},
}

TY  - CPAPER
TI  - RCC8 Is Polynomial on Networks of Bounded Treewidth
AU  - Bodirsky, Manuel
AU  - Wölfl, Stefan
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 756
EP  - 760
DO  - 10.5591/978-1-57735-516-8/IJCAI11-133
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-133
ER  -