资源分类
》 资源 》论文》Variable Elimination in Binary CSP via Forbidden Patterns

Variable Elimination in Binary CSP via Forbidden Patterns

2019-11-11 | |  55 |   38 |   0

Abstract A variable elimination rule allows the polynomialtime identification of certain variables whose elimination does not affect the satisfiability of an instance. Variable elimination in the constraint satisfaction problem (CSP) can be used in preprocessing 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 patterns, in arc-consistent CSP instances. One of these rules is the Broken Triangle Property, whereas the other three are novel. keywords: constraint satisfaction, tractability, arc consis-tency, forbidden pattern.

上一篇：Breaking Symmetries in Graph Representation Michael Codish Alice Miller and Patrick Prosser Peter J. Stuckey

下一篇：Weight-Enhanced Diversification in Stochastic Local Search for Satisfiability Thach-Thao Duong and Duc Nghia Pham and Abdul Sattar and M.A. Hakim Newton

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...