کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431067 | 688265 | 2010 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new upper bound for Max-2-SAT: A graph-theoretic approach
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In MaxSat, we ask for an assignment to the variables which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of O⁎(2K6.265) for Max-2-Sat (each clause contains at most 2 literals), where K is the number of clauses. The run time has been achieved by using heuristic priorities on the choice of the variable on which we branch. The implementation of these heuristic priorities is rather simple, though they have a significant effect on the run time. The analysis uses a non-standard measure. 1
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 8, Issue 4, December 2010, Pages 388–401
Journal: Journal of Discrete Algorithms - Volume 8, Issue 4, December 2010, Pages 388–401
نویسندگان
Daniel Binkele-Raible, Henning Fernau,