Alan K. Mackworth's Publications

Sorted by DateClassified by Publication TypeSorted by First Author Last NameClassified by Author Last Name

Hierarchical Arc Consistency: Exploiting Structured Domains in Constraint Satisfaction Problems

Alan K. Mackworth, J. A. Mulder, and W. S. Havens. Hierarchical Arc Consistency: Exploiting Structured Domains in Constraint Satisfaction Problems. Computational Intelligence, 1(3):118–126, 1985.

Download

[PDF]712.5kB  

Abstract

Constraint satisfaction problems can be solved by network consistency algorithms that eliminate local inconsistencies before constructing global solutions. We describe a new algorithm that is useful when the variable domains can be structured hierarchically into recursive subsets with common properties and common relationships to subsets of the domain values for related variables. The algorithm, HAC, uses a technique known as hierarchical arc consistency. Its performance is analyzed theoretically and the conditions under which it is an improvement are outlined. The use of HAC in a program for understanding sketch maps, Mapsee3, is briefly discussed and experimental results consistent with the theory are reported.

BibTeX

@Article{CI85Alan,
  author =	 {Alan K. Mackworth and J. A. Mulder and W. S. Havens},
  title =	 {Hierarchical Arc Consistency: Exploiting Structured Domains in Constraint Satisfaction Problems},
  year =	 {1985},
  journal =	 {Computational Intelligence},
  volume =       {1},
  number =       {3},
  pages =         {118--126},
  abstract =	 { Constraint satisfaction problems can be solved by network consistency algorithms that eliminate
                   local inconsistencies before constructing global solutions. We describe a new algorithm that is
                   useful when the variable domains can be structured hierarchically into recursive subsets with 
                   common properties and common relationships to subsets of the domain values for related variables. 
                   The algorithm, HAC, uses a technique known as hierarchical arc consistency. Its performance is 
                   analyzed theoretically and the conditions under which it is an improvement are outlined. 
                   The use of HAC in a program for understanding sketch maps, Mapsee3, is briefly discussed and 
                   experimental results consistent with the theory are reported.},
  bib2html_pubtype ={Refereed Journal},
  bib2html_rescat ={},
}

Generated by bib2html.pl (written by Patrick Riley ) on Wed Apr 23, 2014 19:08:34