New Algorithms for Bidirectional Singleton Arc Consistency
المؤلفون المشاركون
Liu, Quan
Zhang, Yonggang
Yin, Qian
Zhu, Xingjun
Li, Zhanshan
Zhang, Sibo
المصدر
Mathematical Problems in Engineering
العدد
المجلد 2013، العدد 2013 (31 ديسمبر/كانون الأول 2013)، ص ص. 1-10، 10ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2013-11-14
دولة النشر
مصر
عدد الصفحات
10
التخصصات الرئيسية
الملخص EN
Bidirectional singleton arc consistency (BiSAC) which is an extended singleton arc consistency (SAC) has been proposed recently.
The first contribution of this paper is to propose and prove two theorems of BiSAC theoretically (one is a property of BiSAC and the other is the property of allowing the deletion of some BiSAC-inconsistent values).
Secondly, based on these properties we present two algorithms, denoted by BiSAC-DF and BiSAC-DP, to enforce BiSAC.
Also, we prove their correctness and analyze the space and time complexity of them in detail.
Besides, for special circumstances, we show that BiSAC-DF admits a worst-case time complexity in O(en2d4) and a best one in O(en2d3) when the problem is an already BiSAC, while BiSAC-DP also has the same best one when the tightness is small.
Finally, experiments on a wide range of CSP instances show BiSAC-DF and BiSAC-DP are usually around one order of magnitude faster than the existing BiSAC-1.
For some special instances, BiSAC-DP is about two orders of magnitude efficient.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Zhang, Yonggang& Yin, Qian& Zhu, Xingjun& Li, Zhanshan& Zhang, Sibo& Liu, Quan. 2013. New Algorithms for Bidirectional Singleton Arc Consistency. Mathematical Problems in Engineering،Vol. 2013, no. 2013, pp.1-10.
https://search.emarefa.net/detail/BIM-1032443
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Zhang, Yonggang…[et al.]. New Algorithms for Bidirectional Singleton Arc Consistency. Mathematical Problems in Engineering No. 2013 (2013), pp.1-10.
https://search.emarefa.net/detail/BIM-1032443
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Zhang, Yonggang& Yin, Qian& Zhu, Xingjun& Li, Zhanshan& Zhang, Sibo& Liu, Quan. New Algorithms for Bidirectional Singleton Arc Consistency. Mathematical Problems in Engineering. 2013. Vol. 2013, no. 2013, pp.1-10.
https://search.emarefa.net/detail/BIM-1032443
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1032443
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر