کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949534 1440196 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The computational complexity of three graph problems for instances with bounded minors of constraint matrices
ترجمه فارسی عنوان
پیچیدگی محاسباتی از سه مسئله گراف برای نمونه هایی با مضامین محدود ماتریس محدود
کلمات کلیدی
برنامه ریزی خطی بولی مشکل تنظیم مستقل، غلبه بر مشکل مجموعه، ماتریکس کوچک، الگوریتم کارآمد،
ترجمه چکیده
ما فرمولاسیون های خطی برنامه ریزی بولی از مجموعه مستقل، رأس و لبه را در نظر می گیریم و مشکالت حل مساله چند جمله ای را برای کلاس های گراف با ماتریس های محدود (اضافه شده) که دارای ارزش های مطلق هستند محدود می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
پیچیدگی محاسباتی از سه مسئله گراف برای نمونه هایی با مضامین محدود ماتریس محدود
چکیده انگلیسی
We consider boolean linear programming formulations of the independent set, the vertex and the edge dominating set problems and prove their polynomial-time solvability for classes of graphs with (augmented) constraint matrices having bounded minors in the absolute value.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 227, 20 August 2017, Pages 13-20
نویسندگان
, ,