Title

Forward checking in the primal and dual constraint graphs.

Date of Award

2005

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Computer Science.

Rights

CC BY-NC-ND 4.0

Abstract

Constraint Satisfaction Problems (CSPs) have been a subject of research in Artificial Intelligence for many years. CSPs are a general way of describing problems that can be used to represent many different types of real-world problems, including scheduling, planning, timetabling, and other combinatorial problems. The primal and dual constraint graphs are two ways of representing a CSP. Some CSPs have features that can be exploited by algorithms trying to find solutions. In this work, results from solving CSPs using forward-checking algorithms that use the primal- and dual-graph representations will be presented, and regions where one representation performs better than the other will be identified. 1t will be shown that the dual representation performs better than the primal representation on CSPs with tight constraints.Dept. of Computer Science. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2005 .P75. Source: Masters Abstracts International, Volume: 44-03, page: 1411. Thesis (M.Sc.)--University of Windsor (Canada), 2005.