Efficient Representation of Discrete Sets for Constraint Programming

Autor:	Hiroaki Tasaka, Naoyuki Tamura, Shuji Ohnishi
Rok vydání:	2003
Předmět:	Constraint (information theory) Discrete mathematics Binary tree AVL tree Binary search tree Computer science Constraint programming Constrained optimization Constraint satisfaction Algorithm Constraint satisfaction problem Domain (software engineering) Set constraint
Zdroj:	Principles and Practice of Constraint Programming – CP 2003 ISBN: 9783540202028 CP ResearcherID
DOI:	10.1007/978-3-540-45193-8_79
Popis:	In constraint solving for finite domains, efficient set representation is an important issue. In this paper we propose an enhancement of Erwig's diet representation called the enhanced diet, which represents a finite domain as an AVL tree of intervals. In addition to element insertion and deletion, we show that the domain splitting used for constraints such as X ≤ Y can be done in O(logm) steps by adopting Crane's Algorithm, where m is the number of intervals, not the number of elements.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ba913a424d2606b8e1f9d2dbd659a7bb https://doi.org/10.1007/978-3-540-45193-8_79 Zobrazit plný text záznamu