微信服务号

微信订阅号

2025-4-24- 14
Home > Archive>Volume 27, Issue 11, 2016 >2701-2711. DOI:10.13328/j.cnki.jos.004874
PDF HTML XML Export Cite reminder
Simple Tabular Reduction for Generalized Arc Consistency on Negative Table Constraints
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61472158, 61272207); Science & Technology Plan of Jilin Province (20140101200JC)

  • Article
    • | |
  • Metrics
    • |
  • Reference
    • |
  • Related
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    Generalized arc consistency (GAC) plays a central role in solving the constraint satisfaction problem. Table constraints can theoretically represent all kinds of constraint relations, and many algorithms have been proposed to establish GAC on table constraints in the past decade. Among these methods, the simple tabular reduction algorithms (STR) are very efficient. However, the existing STR algorithms are suitable for only positive table constraints. They can not directly work on negative table constraints. In this paper, a STR algorithm, called STR-N, is first proposed to directly work on negative table constraints. Then, two improved versions of STR-N, STR-N2 and STR-NIC are presented. Experimental results show that the STR-N algorithms bring improvements over CPU time while solving the instances with negative table constraints.

    Reference
    Related
    Cited by
Get Citation

李宏博,梁艳春,李占山.负表约束的简单表缩减广泛弧相容算法.软件学报,2016,27(11):2701-2711

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 25,2014
  • Revised:January 07,2015
  • Online: November 02,2016
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063