Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning
Abstract
We present a new reasoner for RCC-8 constraint networks, called gp-rcc8, that is based on the patchwork property of path-consistent tractable RCC-8 networks and graph partitioning. We compare gp-rcc8 with state of the art reasoners that are based on constraint propagation and backtracking search as well as one that is based on graph partitioning and SAT solving. Our evaluation considers very large real-world RCC-8 networks and medium-sized synthetic ones, and shows that gp-rcc8 outperforms the other reasoners for these networks, while it is less efficient for smaller networks.
Cite
Text
Nikolaou and Koubarakis. "Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.9115Markdown
[Nikolaou and Koubarakis. "Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/nikolaou2014aaai-fast/) doi:10.1609/AAAI.V28I1.9115BibTeX
@inproceedings{nikolaou2014aaai-fast,
title = {{Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning}},
author = {Nikolaou, Charalampos and Koubarakis, Manolis},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2014},
pages = {2724-2730},
doi = {10.1609/AAAI.V28I1.9115},
url = {https://mlanthology.org/aaai/2014/nikolaou2014aaai-fast/}
}