کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950824 | 1441041 | 2017 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
ترجمه فارسی عنوان
یک الگوریتم زمان چندجملهای برای حداکثر مشکل بزرگنمایی در نمودارهای فاصله مناسب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های گراف، حداکثر برش، نمودار فاصله مناسب
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. On the positive side, the problem is known to be polynomial time solvable in some subclasses of proper interval graphs which is in turn a subclass of chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, and propose a polynomial-time dynamic programming algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 121, May 2017, Pages 29-33
Journal: Information Processing Letters - Volume 121, May 2017, Pages 29-33
نویسندگان
Arman Boyacı, Tinaz Ekim, Mordechai Shalom,