Variable Elimination in Binary CSP via Forbidden Patterns

David Cohen; Martin C Cooper; Guillaume Escamocher; Stanislav Zivný

Variable Elimination in Binary CSP via Forbidden Patterns

David Cohen
, Martin C Cooper
, Guillaume Escamocher
, Stanislav Zivný

Research output: Contribution to conference › Paper › peer-review

172 Downloads (Pure)

Abstract

A variable elimination rule allows the polynomial-
time identification of certain variables whose elim-
ination does not affect the satisfiability of an in-
stance. Variable elimination in the constraint sat-
isfaction problem (CSP) can be used in prepro-
cessing or during search to reduce search space
size. We show that there are essentially just four
variable elimination rules defined by forbidding
generic sub-instances, known as irreducible pat-
terns, in arc-consistent CSP instances. One of these
rules is the Broken Triangle Property, whereas the
other three are novel.

Original language	English
Publication status	Published - 2013
Event	IJCAI - Beijing, China Duration: 3 Aug 2013 → 9 Aug 2013

Conference

Conference	IJCAI
Country/Territory	China
City	Beijing
Period	3/08/13 → 9/08/13

Access to Document

Ccez13ve finalSubmitted manuscript, 125 KB

Cite this

@conference{f5514efffc0d421eac4701a6d7ebc6e3,

title = "Variable Elimination in Binary CSP via Forbidden Patterns",

abstract = "A variable elimination rule allows the polynomial- time identification of certain variables whose elim- ination does not affect the satisfiability of an in- stance. Variable elimination in the constraint sat- isfaction problem (CSP) can be used in prepro- cessing or during search to reduce search space size. We show that there are essentially just four variable elimination rules defined by forbidding generic sub-instances, known as irreducible pat- terns, in arc-consistent CSP instances. One of these rules is the Broken Triangle Property, whereas the other three are novel.",

author = "David Cohen and Cooper, \{Martin C\} and Guillaume Escamocher and Stanislav Zivn{\'y}",

year = "2013",

language = "English",

note = "IJCAI ; Conference date: 03-08-2013 Through 09-08-2013",

}

TY - CONF

T1 - Variable Elimination in Binary CSP via Forbidden Patterns

AU - Cohen, David

AU - Cooper, Martin C

AU - Escamocher, Guillaume

AU - Zivný, Stanislav

PY - 2013

Y1 - 2013

N2 - A variable elimination rule allows the polynomial- time identification of certain variables whose elim- ination does not affect the satisfiability of an in- stance. Variable elimination in the constraint sat- isfaction problem (CSP) can be used in prepro- cessing or during search to reduce search space size. We show that there are essentially just four variable elimination rules defined by forbidding generic sub-instances, known as irreducible pat- terns, in arc-consistent CSP instances. One of these rules is the Broken Triangle Property, whereas the other three are novel.

AB - A variable elimination rule allows the polynomial- time identification of certain variables whose elim- ination does not affect the satisfiability of an in- stance. Variable elimination in the constraint sat- isfaction problem (CSP) can be used in prepro- cessing or during search to reduce search space size. We show that there are essentially just four variable elimination rules defined by forbidding generic sub-instances, known as irreducible pat- terns, in arc-consistent CSP instances. One of these rules is the Broken Triangle Property, whereas the other three are novel.

M3 - Paper

T2 - IJCAI

Y2 - 3 August 2013 through 9 August 2013

ER -