A new arc consistency algorithm for CSPs with hierarchical domains

Author

Kökény, Tibor

Author_Institution

Univ. des Sci. et Tech. du Languedoc, Montpellier, France

fYear

1994

fDate

6-9 Nov 1994

Firstpage

439

Lastpage

445

Abstract

General arc-consistency filtering techniques for constraint satisfaction problems (CSP) can be improved by considering special CSP classes. A domain hierarchical CSP is a CSP in which an intrinsic hierarchical structure of its domains is known. A.K. Mackworth et al. (1985) proposed an are consistency algorithm for domain hierarchical CSPs (HAC) whose worst-case time complexity was 0(md³) where m is the number of constraints and d is the maximal size of a domain. HAC worked only with binary tree structured domains. In this paper we present HAC-6 a new arc-consistency algorithm for domain hierarchical CSPs which works with all types of domain hierarchies (any partial ordering) and its worst-case complexity is 0(md²). HAC-6 is based on AC-6 which is the best at present, worst-case optimal arc-consistency algorithm for classical CSPs

Keywords

computational complexity; constraint handling; HAC-6; arc consistency algorithm; binary tree structured domains; constraint satisfaction problems; domain hierarchies; hierarchical domains; intrinsic hierarchical structure; worst-case time complexity; Algorithm design and analysis; Binary trees; Filtering algorithms; Gaussian processes;

fLanguage

English

Publisher

ieee

Conference_Titel

Tools with Artificial Intelligence, 1994. Proceedings., Sixth International Conference on

Conference_Location

New Orleans, LA

Print_ISBN

0-8186-6785-0

Type

conf

DOI

10.1109/TAI.1994.346459

Filename

346459