oru.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Exploring Directional Path-Consistency for Solving Constraint Networks
QSI, FEIT, University of Technology Sydney, Ultimo NSW, Australia.
QSI, FEIT, University of Technology Sydney, Ultimo NSW, Australia; UTS-AMSS Joint Research Laboratory, AMSS, Chinese Academy of Sciences, Beijing, China.
Örebro University, School of Science and Technology. (AASS)ORCID iD: 0000-0001-7562-2443
2018 (English)In: Computer journal, ISSN 0010-4620, E-ISSN 1460-2067, Vol. 61, no 9, p. 1338-1350Article in journal (Refereed) Published
Abstract [en]

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 state- of-the-art algorithms for solving majority-closed constraints.

Place, publisher, year, edition, pages
Oxford University Press, 2018. Vol. 61, no 9, p. 1338-1350
Keywords [en]
path-consistency, directional path-consistency, constraint networks
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:oru:diva-68857DOI: 10.1093/comjnl/bxx122ISI: 000443557300007OAI: oai:DiVA.org:oru-68857DiVA, id: diva2:1247427
Note

Funding Agencies:

NSFC  11671244 

European-funded H2020 project MoveCare  732158 

Available from: 2018-09-12 Created: 2018-09-12 Last updated: 2018-09-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Sioutis, Michael

Search in DiVA

By author/editor
Sioutis, Michael
By organisation
School of Science and Technology
In the same journal
Computer journal
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf