Exploring directional path-consistency for solving constraint networks

Kong, S; Li, S; Sioutis, M

Exploring directional path-consistency for solving constraint networks

Kong, S Li, S

Sioutis, M

Permalink

Publication Type:: Journal Article
Citation:: Computer Journal, 2018, 61 (9), pp. 1338 - 1350
Issue Date:: 2018-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (671.81 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Kong, S	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.contributor.author	Sioutis, M	en_US
dc.date.available	2020-09-01T19:08:31Z
dc.date.issued	2018-01-01	en_US
dc.identifier.citation	Computer Journal, 2018, 61 (9), pp. 1338 - 1350	en_US
dc.identifier.issn	0010-4620	en_US
dc.identifier.uri	http://hdl.handle.net/10453/133707
dc.description.abstract	© The British Computer Society 2017. All rights reserved. Among the local consistency techniques used for solving constraint networks, path-consistency (PC) has received a great deal of attention. However, enforcing PC is computationally expensive and sometimes unnecessary. Directional PC (DPC) is a weaker notion of PC that considers a given variable ordering and can thus be enforced more efficiently than PC. This paper shows that (the DPC enforcing algorithm of Dechter and Pearl) decides the constraint satisfaction problem (CSP) of a constraint language if it is complete and has the variable elimination property (VEP). However, we also show that no complete VEP constraint language can have a domain with more than two values. We then present a simple variant of the algorithm, called, and show that the CSP of a constraint language can be decided by if it is closed under a majority operation. In fact, is sufficient for guaranteeing backtrack-free search for such constraint networks. Examples of majority-closed constraint classes include the classes of connected row-convex constraints and tree-preserving constraints, which have found applications in various domains, such as scene labeling, temporal reasoning, geometric reasoning and logical filtering. Our experimental evaluations show that significantly outperforms the stateof-the-Art algorithms for solving majority-closed constraints.	en_US
dc.relation.ispartof	Computer Journal	en_US
dc.relation.isbasedon	10.1093/comjnl/bxx122	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	Exploring directional path-consistency for solving constraint networks	en_US
dc.type	Journal Article
utslib.citation.volume	9	en_US
utslib.citation.volume	61	en_US
utslib.for	0805 Distributed Computing	en_US
utslib.for	08 Information and Computing Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
pubs.organisational-group	/University of Technology Sydney/Students
utslib.copyright.status	open_access
pubs.issue	9	en_US
pubs.publication-status	Published	en_US
pubs.volume	61	en_US

Abstract:

© The British Computer Society 2017. All rights reserved. Among the local consistency techniques used for solving constraint networks, path-consistency (PC) has received a great deal of attention. However, enforcing PC is computationally expensive and sometimes unnecessary. Directional PC (DPC) is a weaker notion of PC that considers a given variable ordering and can thus be enforced more efficiently than PC. This paper shows that (the DPC enforcing algorithm of Dechter and Pearl) decides the constraint satisfaction problem (CSP) of a constraint language if it is complete and has the variable elimination property (VEP). However, we also show that no complete VEP constraint language can have a domain with more than two values. We then present a simple variant of the algorithm, called, and show that the CSP of a constraint language can be decided by if it is closed under a majority operation. In fact, is sufficient for guaranteeing backtrack-free search for such constraint networks. Examples of majority-closed constraint classes include the classes of connected row-convex constraints and tree-preserving constraints, which have found applications in various domains, such as scene labeling, temporal reasoning, geometric reasoning and logical filtering. Our experimental evaluations show that significantly outperforms the stateof-the-Art algorithms for solving majority-closed constraints.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/133707