On Broken Triangles
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 4135-4138.
Abstract
A binary CSP instance satisfying the broken-triangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in binary CSPs, thus providing a novel polynomial-time reduction operation. Experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances of arbitrary arity. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP.
@inproceedings{ijcai2016p617,
title = {On Broken Triangles},
author = {Cooper, Martin C. and El Mouelhi, Achref and Terrioux, Cyril and Zanuttini, Bruno},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {4135--4138},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/617},
}
TY - CPAPER TI - On Broken Triangles AU - Cooper, Martin C. AU - El Mouelhi, Achref AU - Terrioux, Cyril AU - Zanuttini, Bruno T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 4135 EP - 4138 UR - https://ijcai.org/proceedings/2016/617 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
